【每日一题】【面试经典150 | 动态规划】爬楼梯

Tag

【动态规划】【数组】

---

题目来源

70. 爬楼梯

---

题目解读

有过刷题「动态规划」刷题经验的读者都知道，爬楼梯问题是一种最典型也是最简单的动态规划问题了。

题目描述为：你每次可以爬 1 或者 2 个台阶，问爬上 n 阶有多少种方式。

---

解题思路

方法一：动态规划

思路

动态规划问题是有固定的解题套路的。

首先是状态的选择，本题中的转态为 f[i]，表示爬上 i 阶楼梯的方案数。

接着是转态转移，即 f[i] 是如何递推得到的。因为「每次可以爬 1 阶 或者 2 阶楼梯」，所以可以从 i-1 阶楼梯爬到 i 阶，也可以从 i-2 阶楼梯爬到 i 阶。因此有
转移关系：

$$f[i]=f[i-1]+f[i-2]$$

然后是 base case，base case 就是递推的初始值，本题中为 f[0] = 1 和 f[1] = 1。

最后返回 f[n]，表示爬上 n 阶楼梯的方案数。

代码

class Solution {
public:int climbStairs(int n) {vector<int> dp(n+1);dp[0] = dp[1] = 1;for (int i = 2; i <= n; ++i) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
};

复杂度分析

时间复杂度：$O(n)$。

空间复杂度：$O(n)$。

方法二：滚动数组

思路

观察方法一中的状态转移方式发现，每个状态的值只和上一个以及上上个状态的值有关，于是可以使用两个变量来存储上一个以及上上个状态的值，这样就可以将时间复杂度从 $O(n)$ 优化到 $O(1)$。

算法

class Solution {
public:int climbStairs(int n) {int p = 0, q = 0, r = 1;for (int i = 1; i <= n; ++i) {p = q;q = r;r = p + q;}return r;}
};

复杂度分析

时间复杂度：$O(n)$。

空间复杂度：$O(1)$。