思路:
- 数学归纳法,找规律,解得f(n)=
- 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];
}
};