70.爬楼梯

问题

假设你正在爬楼梯。需要 \(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);
    }
}