leetcode-70 爬楼梯(java实现)
标签： leetcode-70 爬楼梯(java实现) MySQL博客 51CTO博客
2023-06-13 18:24:05 231浏览
爬楼梯
- 题目
- 分析1 递归写法
- 动态规划解法
题目
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
分析1 递归写法
如果要爬上第n阶，要么是从第n-1上面再爬1阶上去的，要么是从n-2上面再爬2阶上去的，那么我们就可以想到 f(n) = f(n-1)+f(n-2),这样也就很容易利用递归写出来
public static int climbStairs(int n) {
// 这个貌似也是要用到递归，把之前的n-1个台阶的步骤全部加起来就可以了
if(n == 1){
return 1;
}else if(n == 2){
return 2;
}else{
return climbStairs(n-1)+climbStairs(n-2);
}
}递归树的高度为n，每个节点有2个子节点，所以总共需要计算的节点数为2的n次方。因此，时间复杂度为O(2^n)
空间复杂度也比较高，因为每个递归函数调用都会创建一个新的栈帧，占用一定的内存。递归树的深度为n，所以空间复杂度为O(n)。
提交后，leetcode 平台提示运行失败，超时了
本地是能正常输出的，写法和思路是没有问题的，不过确实慢
动态规划解法
假设到达第i个楼梯的不同方法数为dp[i]，则有以下递推式：
dp[i] = dp[i-1] + dp[i-2]
因为每次只能爬1个或2个楼梯，所以到达第i个楼梯的方法数等于到达第i-1个楼梯的方法数加上到达第i-2个楼梯的方法数。
初始状态为dp[1]=1和dp[2]=2，因为到达第1个楼梯只有1种方法，到达第2个楼梯有2种方法（一次跨2个或者分两次跨1个）。
最终要求的答案是到达第n个楼梯的方法数，即dp[n]。
public int climbStairs(int n) {
if (n == 1) return 1;
// 当需要计算到 dp[n] 时，数组下标是从 0 到 n 的，需要定义一个长度为 n+1 的数组才能存储计算结果。如果定义一个长度为 n 的数组，那么在计算 dp[n] 的时候，就会发生数组越界的错误
int[] dp = new int[n+1];
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)，空间复杂度为O(n)。
提交后的结果成功
好博客就要一起分享哦！分享海报
此处可发布评论
评论（0）展开评论
展开评论
