变态跳台阶
C++，还是动态规划。
有一种延续上一个题的笨方法，就是f(n) = f(n-1) + f(n-2) + ... f(2) + f(1) + 1，双重循环复杂度O(n)。
其实如果仔细看的话就发现一个规律了，如下规律：
f(1) = 1, f(0) = 1f(2) = 1 = f(1) + 1 = 2 * f(1)f(3) = f(2) + f(1) + 1 = f(2) + f(2) = 2f(2)- 同理
f(4) = 2f(3)…f(n) = 2f(n-1)
所以状态转移公式就是：
dp[n] = 2 * dp[n-1], n >= 2dp[1] = 1
代码如下：
class Solution {
public:
int jumpFloorII(int number) {
int dp[50];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= number; i++) dp[i] = 2 * dp[i-1];
return dp[number];
}
};
