70. Climbing Stairs

问题

这个问题是说，我们在爬台阶，一次只能上一阶或者2阶，设计一个算法，求爬n阶台阶有多少种方式。n>= 1 && n <= 45。

解析

这个题的思路在于，walk through一个在某一阶的例子，就会明白很多。

比如你在第i阶，达到这阶的方法要么是第i-1阶上了1阶，要么是i-2阶上了2阶上到这里的。那么我们就出现子问题了，dp[i] = dp[i - 1] + dp[i - 2]，这里dp[i]的含义就是能够上到第i阶有多少种方式（结果、状态）就这样，你已经把动态规划的状态转移公式写出来了。

初始化。当有1阶的时候，dp[1] = 1，当有0阶的时候，这里的想法是，没有台阶，那么上到0阶的方式就是1种，dp[0] = 1（不是0）。

这里如果dp[0]不好理解的话，因为n的取值是1-45，可以将初始化设置dp[1]和dp[2]。

代码

class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[0] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 2] + dp[i - 1];
        }
        return dp[n];
    }
}

代码2（优化）

我们发现当前的状态只与他之前的两个状态（结果）有关，那么我们可以不设置一个dp数组而只利用三个变量即可不断更新状态。如下图所示，在下一次迭代的时候，所有的指向都向前走了一位。原来的dp_0被丢弃，原来的dp_1成为现在的dp_0，原来的dp_i成为现在的dp_1, 原来的dp_(i + 1)成了现在的dp_i。

|dp_0|dp_1|res| |

|~~dp_0~~|dp_0|res = (dp_0 + dp_1) -> dp_1|res|

class Solution {
    public int climbStairs(int n) {
        int dp_0 = 1;
        int dp_1 = 1;
        if (n < 2) return 1;
        int res = 0;
        for (int i = 2; i <= n; i++) {
            res = dp_0 + dp_1;
            dp_0 = dp_1;
            dp_1 = res;
        }
        return res;
    }
}

1. Climbing Stairs

Problem

This problem says that we are climbing steps, one or two at a time. Design an algorithm to find how many ways to climb n steps. n>= 1 && n <= 45.

Solution

The idea of this problem is that walking through an example at a particular step makes a lot more sense.

For example, if you are at order i, the way to reach this order is either order i-1 up to order 1, or order i-2 up to order 2 up to here. Then we have the subproblem, dp[i] = dp[i - 1] + dp[i - 2], where the meaning of dp[i] is how many ways (results, states) to be able to go up to order i. That's it, you've written out the state transfer formula for dynamic programming.

Initialization. When there is a 1st order, dp[1] = 1, when there is a 0th order, the idea here is that there is no step, then there is 1 way to go up to the 0th order, dp[0] = 1 (not 0).

Here if dp[0] is not well understood, because n takes values from 1-45, you can set initialization to dp[1] and dp[2].

Code

class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[0] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 2] + dp[i - 1];
        }
        return dp[n];
    }
}

Code 2 (optimization)

We find that the current state is related to only two of his previous states (results), so instead of setting up a dp array we can just use three variables to keep the state updated. As shown in the figure below, on the next iteration, all the pointers are moved forward by one bit. The original dp_0 is discarded, the original dp_1 becomes the current dp_0, the original dp_i becomes the current dp_1, and the original dp_(i + 1) becomes the current dp_i.

|dp_0|dp_1|res| |

|~~dp_0~~|dp_0|res = (dp_0 + dp_1) -> dp_1|res|

class Solution {
    public int climbStairs(int n) {
        int dp_0 = 1;
        int dp_1 = 1;
        if (n < 2) return 1;
        int res = 0;
        for (int i = 2; i <= n; i++) {
            res = dp_0 + dp_1;
            dp_0 = dp_1;
            dp_1 = res;
        }
        return res;
    }
}