Appearance
题目
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶提示：
- 1 <= n <= 45
理解题目
这种就是像数学一样，举个例子从 1 到 10，总共有多少中加法的意思。我第一次可以上一阶或者上两阶，只要最后能到的最高的那层一共有多少种上法。
题解
这道题倒着分析，更容易找到突破口，因为题目中讲了一次只能上 1 阶或者 2 阶。要么就是从 n-1 层跳上来，要么就是 n-2 层跳上来的 再看看题目中的例子，当 n=3 时，要么是从第一阶上来要么就是从第二阶上来的，如果是第一阶上来的，还剩下两个台阶，可以一次性走完或者一阶一阶走。所以他的总数等于 2+1 当 n=4 时，同样要么是倒数第一层或者是倒数第二层上来的，如果是倒数第一层来的，那我们就去求上到倒数第一层的上法有多少总，倒数第一层不就是我们的 n=3 的时候吗？接着倒数第二层，不就是我们 n=2 的时候吗？
是不是很熟悉了，这种数学归纳法的气息都在上面了，
上面可以知道状态转移方程是 dp[i]=dp[i-1]+dp[i-2]
答案
简易版
ts
function climbStairs(n: number): number {
if(n<2) return 1
let dp = new Array(n).fill(0)
dp[0] = 1
dp[1] = 1
for(let i=2;i<=n;i++){
dp[i] = dp[i-1]+dp[i-2]
}
return dp[n]
};function climbStairs(n: number): number {
if(n<2) return 1
let dp = new Array(n).fill(0)
dp[0] = 1
dp[1] = 1
for(let i=2;i<=n;i++){
dp[i] = dp[i-1]+dp[i-2]
}
return dp[n]
};进化版
ts
function climbStairs(n: number): number {
if (n < 2) return 1;
let dp0 = 1;
let dp1 = 1;
for (let i = 2; i <= n; i++) {
const temp = dp0;
dp0 = dp1;
dp1 = dp1 + temp;
}
return dp1;
}function climbStairs(n: number): number {
if (n < 2) return 1;
let dp0 = 1;
let dp1 = 1;
for (let i = 2; i <= n; i++) {
const temp = dp0;
dp0 = dp1;
dp1 = dp1 + temp;
}
return dp1;
}