问题
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶
解答1
此题目可以说是最经典（另一种说法是最“容易”）的动态规划的题目。
动态规划是将一个大问题分解为多个简单的子问题来求解的方法。
动态规划常常适用于有重叠子问题与最优子结构的问题。
思路
- 设f(n)为总的方法数量
- 可以看到，到第n阶的方法其实一共有两种方式
- 从第n−1阶爬一步到达第n阶
- 从第n−2阶爬两步到达第n阶
- 因此可以总结出公式
\begin{cases}
1, & \text{$n = 1$} \\
2,& \text{$n = 2$} \\
f(n-1) +f(n-2), & \text{$n>2$}
\end{cases}$$可以发现，这个就是斐波那契数列的变种。
#代码1
## java实现
```java
class Solution {
public int climbStairs(int n) {
return resolve(n);
}
public int resolve(int n) {
if (n==1) {
return 1;
}
if (n==2) {
return 2;
}
return resolve(n-1)+resolve(n-2);
}
}
```
代码非常的简洁，马上丢到leetcode上跑一次，居然执行了10801 ms。击败了0.98%的人。。。
# 解法2
解法1虽然勉强能跑，但是有一个非常严重的问题是，重复计算量过大。
$f(n)$与$f(n-1)$均用到了$f(n-2)$但是因为并没有暂存的地方，导致$f(n-2)$被计算了两次。
比如计算$f(5)$：
```dot
strict graph {
a -- b
a -- b
b -- a [color=blue]
}
```
此时考虑到以往的数据会被重复使用，那么何不做一个数组暂存数据呢。
# 代码2
## java实现
```java
class Solution {
public int climbStairs(int n) {
int[] cache = new int[n+1];
return resolve(n);
}
public int resolve(int n, int[] cache) {
if (n==1) {
return 1;
}
if (n==2) {
return 2;
}
if (cache[n] ==0) {
cache[n] = resolve(n-1,cache) +resolve(n-2,cache);
}
return cache[n];
}
}
```
此方法4ms执行完成。
# 解法3
上述两种方法，均是递归调用，如何转为迭代呢？
# 代码3
## java实现
```java
class Solution {
public int climbStairs(int n) {
int[] cache = new int[n+1];
cache[0] = cache[1] = 1;
for(int i=2;i<=n;i++) {
cache[i] = cache[i-1] + cache[i-2];
}
return cache(n);
}
}
```