【LeetCode】70.爬楼梯
LeetCode70 爬楼梯题解
题目
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入：n = 2——输出： 2
解释： 有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶
示例 2：
输入： n = 3——输出： 3
解释： 有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶
解题思路
思路1 递归求解
我们从最后一级台阶n开始分析，有两种方法可以上去，n-1爬一次即可，n-2需要两个台阶即可到达第n个台阶,问题本质是斐波那契数列。
用数学公式表示就是:
f(n) = f(n-1) + f(n-2)
递归是这样理解把它拆分出来，两个字，递和归
递：递推（这就需要找到递推公式）
归：回归（需要找到回归条件，递推过程逐渐逼近回归条件）
代码如下
int climbStairs(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
return climbStairs(n-1) + climbStairs(n-2);
}
运行能通过
提交不能通过，超出时间限制了，时间复杂度是O（2^n）
时间复杂度为O(2^n)，空间复杂度O(n)
通过观察我们发现出现很多重复计算的地方（图中画圈的地方），其实是这些地方增加n了时间的消耗。为了解决这个问题，我们想象一下，把每次计算的数据存起来，下次用到的时候就不用计算，直接返回。而以下的记忆递归就可以解决这个问题。
思路2 全部累加
当前层爬楼梯方法数等于前两层爬楼梯数相加
#include <stdio.h>
#include <stdlib.h>
int climbStairs(int n)
{
int *arr = (int *)malloc((n + 1) * sizeof(int));
// arr[0] = 0; //不用
arr[1] = 1; // 第一步
arr[2] = 2; // 第二步
if (1 == n)
return 1;
else if (2 == n)
return 2;
for (int i = 3; i <= n; i++) // a[3]-最后
{
arr[i] = arr[i - 1] + arr[i - 2]; // 前一个 + 前面的第二个
}
return arr[n];
}
int main()
{
int n = 5;
int result = climbStairs(n);
printf("result = %d\n", result);
return 0;
}
在vscode里运行是没有问题的，放到力扣里就报错了
Line 16: Char 12: runtime error: store to address 0x602000000098 with insufficient space for an object of type 'int' [solution.c]
0x602000000098: note: pointer points here
01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
^
修改一下代码的顺序，先判断n是否是1或者2，如果是的话，直接返回对应的结果，如果是3到最后一个的台阶，则带入计算，为了方便观察是第几级台阶，这里我不使用arr[0]这个变量，从arr[1]开始算，代码如下所示：
int climbStairs(int n) {
int *arr = (int *)malloc((n+1) * sizeof(int));
if(1 == n)
return 1;
else if (2 == n)
return 2;
// arr[0] = 0; //不用
arr[1] = 1; //第一步
arr[2] = 2; //第二步
for(int i = 3; i <= n; i++) //a[3]-最后
{
arr[i] = arr[i-1] + arr[i-2]; //前一个 + 前面的第二个
}
return arr[n];
}
啊啊啊，通过了 ~ ~ ~
思路3 动态规划
动态规划解析：
状态定义： 设 dp 为一维数组，其中 dp[i] 的值代表斐波那契数列的第 i 个数字。
转移方程： dp[i+1]=dp[i]+dp[i−1] ，即对应数列定义 f(n+1)=f(n)+f(n−1) 。
初始状态： dp[0]=1, dp[1]=1 ，即初始化前两个数字。
返回值： dp[n] ，即斐波那契数列的第 n 个数字。
状态压缩：
若新建长度为 n 的 dp 列表，则空间复杂度为 O(N) 。
由于 dp 列表第 i 项只与第 i−1 和第 i−2 项有关，因此只需要初始化三个整形变量 sum, a, b ，利用辅助变量 sum 使 a,b 两数字交替前进即可 （具体实现见代码） 。由于省去了 dp 列表空间，因此空间复杂度降至 O(1) 。
作者：Krahets
链接：https://leetcode.cn/problems/climbing-stairs/solutions/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
class Solution {
public:
int climbStairs(int n) {
int a = 1, b = 1, sum;
for(int i = 0; i < n - 1; i++){
sum = a + b;
a = b;
b = sum;
}
return b;
}
};
作者：Krahets
链接：https://leetcode.cn/problems/climbing-stairs/solutions/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
复杂度分析：
时间复杂度 O(n) ： 计算 f(n) 需循环 n 次，每轮循环内计算操作使用 O(1) 。
空间复杂度 O(1) ： 几个标志变量使用常数大小的额外空间。
参考文章
https://leetcode.cn/problems/climbing-stairs/solutions/2361764/70-pa-lou-ti-dong-tai-gui-hua-qing-xi-tu-ruwa/
https://blog.csdn.net/2302_80105876/article/details/135863529?fromshare=blogdetail&sharetype=blogdetail&sharerId=135863529&sharerefer=PC&sharesource=weixin_63135906&sharefrom=from_link
https://jerryzhou.blog.csdn.net/article/details/99673621?fromshare=blogdetail&sharetype=blogdetail&sharerId=99673621&sharerefer=PC&sharesource=weixin_63135906&sharefrom=from_link
原文地址：https://blog.csdn.net/weixin_63135906/article/details/143752447
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！