272.Climbing StairsII

1.Description(Easy)

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

2.Code

我们用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层的所有走法里了。

state: f(i)

function:f(i)=f(i-1)+f(i-2)+f(i-3)

initialize: f(0)=1; f(1)=1; f(2)=2;

public int climbStairs2(int n) {
        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];
    }