题目描述 变态跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
解题思路
简单动态规划：
- 当n = 1 时，只有1阶跳：dp(1) = 1;
- 当n = 2 时，有一阶跳和二阶跳两种方式：dp(2) = 2;
- 当n = 3 时，有三种跳的方式，第一次跳出一阶后，剩下的（3-1）个台阶有dp(3-1)种跳法； 第一次跳出二阶后，剩下的（3-2）个台阶有对应dp(3-2)种跳法；直接跳到第三阶。dp(3) = dp(2) + dp(1)+ 1 = 4;
- 可推导出当n = n时，dp(n) = dp(n-1) + dp(n-2) + ....... + dp(1) + 1;
- 观察到dp(n-1) = dp(n-2) + ....... + dp(1) + 1，因此可得dp(n) = 2*dp(n-1);
DP
DP定义：记dp[i]为青蛙跳上一个i+1级的台阶的总跳法；
DP初始：dp[0] = 1，dp[1] = 2;
DP更新：dp[i] = 2*dp[i-1] ；
代码
class Solution {
public:
int jumpFloorII(int number) {
vector<int> dp(number, 0);
dp[0]=1;
dp[1]=2;
for(int i=2;i<number;i++){
dp[i] += 2 * dp[i-1];
}
return dp[number-1];
}
};
