[LintCode] 272 Climbing Stairs II 解题报告

Description
A child is running up a staircase with n steps, and can hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible ways the child can run up the stairs.


Example
n=3
1+1+1=2+1=1+2=3=3
return 4


思路
                             ｜——
                 ｜——      3
      ｜——     2
——    1
 0

我们用f[i]来表示从底层跳到第i层有多少种方法。
我们看最底层是第0层，小人本来就在那里。所以初始化f[0] = 1。
跳到第1层，只有1种跳法。所以初始化f[1] = 1。
跳到第2层，有2种方法。从0直接跳到2，或者从0跳到1再跳到2。所以f[2] = 2。
其实第i层的跳法就是之前三层的走法的和。f[i] = f[i - 1] + f[i - 2] + f[i - 3]。
因为从这3层，分别有从i - 3层跳3格，从i - 2层跳2格，以及从i - 1层跳1格的走法。
注意，从i - 3层先跳到i - 2层再直接跳到i层，这个走法，已经包含在跳到i - 2层的所有走法里了。


Code

public class Solution {
    /**
     * @param n an integer
     * @return an integer
     */
    public int climbStairs2(int n) {
        // Write your code here
        if (n <= 1) {
            return 1;
        }
        int[] f = new int[n + 1];
        f[0] = 1;
        f[1] = 1;
        f[2] = 2;
        for (int i = 3; i <= n; i++) {
            f[i] = f[i - 1] + f[i - 2] + f[i - 3];
        }
        return f[n];
    }
}