39.变态跳台阶

思路：

1. 数学归纳法，找规律，解得f(n)=
2. DP,f(n)=f(n-1)+f(n-2)+...+f(1)

代码：

class Solution {
public:
    int jumpFloorII(int number) {
        int ret=1;
        for(int i=0;i<number-1;i++)
            ret*=2;
        return ret;
    }
};

dp

class Solution {
public:
    int jumpFloorII(int n) {
        vector<int> dp(n+1,0);
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<=n;i++)
            for(int j=0;j<i;j++)
                dp[i]+=dp[j];
        
        return dp[n];
    }
};