Leetcode日记：70.爬楼梯

爬呀爬呀爬楼梯
爬呀爬呀爬楼梯

题目

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

1
2
3
4
5
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

1
2
3
4
5
6
Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

分析

题目很容易理解，可以选择一次爬两节台阶，也可以爬一节，问究竟有多少种情况（不能忽略顺序）。
这道题和53题的最长子串题有异曲同工之妙，为什么这么说呢？
首先我们来看：
最长字串要对前面计算的子串长度进行更新，在更新的过程中，势必要得出在之前的最长字串是多少。
而爬楼梯这道题，同样和前一状态有关，比如爬n节台阶，就会分为两种情况：

  • 在n-1的台阶处爬一层台阶
  • 在n-2的台阶处爬两层台阶

继续向下延伸思考，到达每一次层一共有几种方法这个问题就变成了2个子问题：

  • 到达n-1层台阶有几种方法
  • 到达n-2层台阶有几种方法

动态规划

通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法，这就是动态规划。动态规划常常适用于有重叠子问题和最优子结构性质的问题。我们要明确，动态规划是一种思想，并不是一种具体的算法。

那么适用于动态规划的问题都有哪些特征呢？

  • 最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。
  • 重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。

回到原问题

让我们回归这道题，我们总结一下之前分析的结果：

第n个结果=第n-1个结果+第n-2个结果

好的，我们抛开我们熟悉的斐波那契数列不谈（事实上，在只能走1，2节的时候该题的结果就是斐波那契数列。。），我们可以建立一个dp数组，先将1和2两种情况求出来，之后的3、4、…、n+1都可以用前两个已经计算出的子结果得到。

这就是我们这道题利用到动态规划的核心算法。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

代码源文件

总结

动态规划问题算法多变，需要多做题熟练掌握这种思想。