问题

假设你正在爬楼梯。需要 \(n\) 阶你才能到达楼顶。

每次你可以爬 \(1\) 或 \(2\) 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 \(n\) 是一个正整数。

示例 1：

输入： \(2\)
输出： \(2\)
解释： 有两种方法可以爬到楼顶。

1. \(1\) 阶 + \(1\) 阶
2. \(2\) 阶

示例 2：

输入： \(3\)
输出： \(3\)
解释： 有三种方法可以爬到楼顶。

1. \(1\) 阶 + \(1\) 阶 + \(1\) 阶
2. \(1\) 阶 + \(2\) 阶
3. \(2\) 阶 + \(1\) 阶

解答1

此题目可以说是最经典（另一种说法是最“容易”）的动态规划的题目。
动态规划是将一个大问题分解为多个简单的子问题来求解的方法。
动态规划常常适用于有重叠子问题与最优子结构的问题。

思路

1. 设\(f(n)\)为总的方法数量
2. 可以看到，到第\(n\)阶的方法其实一共有两种方式
   • 从第\(n-1\)阶爬一步到达第\(n\)阶
   • 从第\(n-2\)阶爬两步到达第\(n\)阶
3. 因此可以总结出公式
   \(f(n) = \begin{cases} 1, & \text{\)n = 1\(} \\ 2,& \text{\)n = 2\(} \\ f(n-1) +f(n-2), & \text{\)n>2\(} \end{cases}\)可以发现，这个就是斐波那契数列的变种。

##代码1

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)\)：

    
    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实现

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);
    }
}