本文最后编辑于 前，其中的内容可能需要更新。
力扣70. 爬楼梯题解
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
1
2
3
4
5
6
| 输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
|
示例 2：
1
2
3
4
5
6
7
| 输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
|
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/climbing-stairs
首先看到爬楼梯那么解法第一个肯定就是递归(上次写过)
1
2
3
4
5
6
7
8
9
10
11
12
13
| 0层楼梯：1种方法
1层楼梯：1种方法
2层楼梯：2种方法 1+1，2
3层楼梯：3种方法 1：(3-1) = 2层楼梯 2：(3-2) = 1层楼梯
n：楼梯数
f(n)：有多少方法可以到达楼顶
f(n) = f(n - 1) +f(n - 2)
|
so easy！
代码
1
2
3
4
5
6
7
8
| class Solution {
public int climbStairs(int n) {
if(n == 0) return 1;
if(n == 1) return 1;
return climbStairs(n - 1)+climbStairs(n - 2);
}
}
|
结果
漂亮，超时了
那么就是我们在递归的过程中大量的重复运算了之前的数据，那我们可以用动态规划来优化
动态规划是什么？就是缓存了一堆数据的迭代，我们把之前计算过的结果缓存下来，就可以减少运算量
首先我们需要一个数组储存运算结果
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int climbStairs(int n) {
int size = 10000;
int[] f = new int[size];
f[0] = 1;
f[1] = 1;
for(int i = 2; i <= n; i++)
{
f[i] = f[i - 1] + f[i - 2];
}
return f[n];
}
}
|
结果
