Leetcode—70.爬楼梯【简单】

2023每日刷题（二十七）

Leetcode—70.爬楼梯

在这里插入图片描述

动态规划思想

动态规划算法的本质是使用空间换时间，通过计算和记录状态来得到最优解。

在分析动态规划类题目时，我们可以通过3个问题对题目进行基本的拆解。

1.问题是否分阶段，阶段是什么？
2.与问题的最优解有关的子问题是什么？
3.透过不同阶段、最优解和子问题，我们应当关注（计算和记录）的状态具体是什么？

前两个问题比较容易回答。

1.爬楼梯是分阶段的，到达楼顶所需的n级台阶即对应的n个阶段。

2.题目的最优解是指最终到达楼顶，有多少种不同的实现方法；每个阶段都可以对应一个子问题，即有多少种不同的方法可以到达当前台阶。

关键在于第3个问题。根据题目描述“每次可以爬1或2个台阶”，这句话定义了状态之间的关联关系，决定了状态转移的规则。

假设当前台阶为n，上述规则决定了我们可以通过两个阶段到达这里：从n-1台阶爬1步，或者从n-2台阶爬2步，因此到达台阶n可能的方法总数等于到达台阶n-1和台阶n-2的可能总数之和，这符合我们看到题目时马上会有的“直觉”，越往上走可能的走法越多。

使用数组dp记录到达每一个台阶可能的方法数，上述逻辑可以表示为dp[i]=dp[i-1]+dp[i-2]。通过这个状态转移函数，我们可以从1级台阶、2级台阶开始计算出到达3级台阶、4级台阶乃至n级台阶不同方法的总量。

实现代码

int climbStairs(int n) {
    int dp[50] = {0};
    if(n < 2) {
        return n;
    }
    dp[1] = 1;
    dp[2] = 2;
    for(int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

运行结果

在这里插入图片描述
●　时间复杂度：O(n)，n为台阶数。
●　空间复杂度：O(n)，n为台阶数。

动态规划优化算法思路

观察解法一，每次计算用到的被记录状态都是dp[i-1]、dp[i-2]，除非有其他需要，否则单纯计算最终解并不用保留中间过程的结果，dp[i]对dp[i-1]和dp[i-2]的依赖使用两个变量即可记录，例如，定义变量first和second。用常数个变量代替长度为n的线性存储结构，使空间复杂度由O(n)降低至O(1)，在提高存储效率的同时执行效率也会得到提升。

优化算法后实现代码

int climbStairs(int n) {
    int dp[50] = {0};
    if(n < 2) {
        return n;
    }
    int first = 1;
    int second = 2;
    for(int i = 3; i <= n; i++) {
        second = first + second;
        first = second - first;
    }
    return second;
}