Leetcode 70.爬楼梯题解
题目描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
输入示例
1 2 3 4 5 输入：n = 2 输出：2 解释：有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶
1 2 3 4 5 6 输入：n = 3 输出：3 解释：有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶
解题思路
这是一道非常标准的dp入门题
不如我们先从回溯角度可以写
设n=4 我们可以从反反向跳下去 每次可以跳1或者2格 因此 我们可以得出 (i-1) 和(i-2) 求方案总数
所以最终方程是dfs(i-1)+dfs(i-2)
那么另外一个问题来了 终止条件是什么？
从i-2看到 所以i必须大于2 因为答案不可能是负数
递归代码如下**(Python 和 C++)**
1 2 3 4 5 6 7 8 class Solution : def climbStairs (self, n: int ) -> int : def dfs (i ): if i < 2 : return i return dfs(i-1 ) + dfs(i-2 ) return dfs(n+1 )
1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution {public : int dfs (int n) if (n < 2 ){return n;} return dfs (n-1 )+dfs (n-2 ); } int climbStairs (int n) return dfs (n+1 ); } };
你提交之后 会发现 唉？ 超时了
因为递归会造成大量重复计算
从刚才那个例子开始 比如我执行了一次 dfs(n-2) 相当于执行了两次dfs(n-1) 这样会拖慢时间
因此我们可以改成 记忆化搜索 保存计算结果 Python 可以用cache装饰器 c++得自己开数组 代码如下
1 2 3 4 5 6 7 8 9 class Solution : def climbStairs (self, n: int ) -> int : @cache def dfs (i ): if i < 2 : return i return dfs(i-1 ) + dfs(i-2 ) return dfs(n+1 )
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution {public : int ans[50 ]; int dfs (int n) if (n < 2 ){return n;} if (ans[n] != 0 ){return ans[n];} int res = dfs (n-1 )+dfs (n-2 ); ans[n] = res; return res; } int climbStairs (int n) for (int i = 0 ; i < 50 ; i++){ ans[i] = 0 ; } return dfs (n+1 ); } };
ok 那我们能不能把递归去掉 把他改成迭代呢？
接下来 我们1:1 把递归翻译成动态方程
1 2 dfs(i) = dfs(i-1)+dfs(i-2) f[i] = f[i-1]+f[i-2]
好 现在边界条件是f[0] = 1 f[1] = 2
写一个从2开始的循环(注意：要循环次数要小于等于n)
以下是代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution {public : int ans[50 ]; int climbStairs (int n) if (n==2 ){return 2 ;} if (n==1 ){return 1 ;} ans[0 ] = 1 ; ans[1 ] = 2 ; for (int i = 2 ; i < n; i++){ ans[i] = ans[i-1 ]+ans[i-2 ]; } return ans[n-1 ]; } };
1 2 3 4 5 6 7 8 9 10 11 class Solution : def climbStairs (self, n: int ) -> int : dp = [0 for _ in range (n+1 )] dp[0 ] = 1 dp[1 ] = 2 for i in range (2 ,n+1 ): dp[i] = dp[i-1 ]+dp[i-2 ] return dp[n-1 ]
这里又有一个规律
dp[i-1] 是上一个状态 dp[i-2] 是上上个状态
我们能不能用两个变量维持这个状态呢？ 见示例代码
示例代码
1 2 3 4 5 6 7 8 9 10 class Solution : def climbStairs (self, n: int ) -> int : if n <= 2 : return n a = 1 b = 2 for i in range (2 ,n): a, b = b, a + b return b
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution {public : int climbStairs (int n) if (n<=2 ){return n;} int a = 1 , b = 2 ; for (int i = 2 ; i < n; i++){ int nxt = b; b+=a; a = nxt; } return b; } };
感谢收看
