变态跳台阶
题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
分析：
DP(n)代表跳上第n级台阶的次数。
DP(0) = 1
DP(1) = DP(1 - 1)
DP(2) = DP(2 - 1) + DP(2 - 2)
DP(3) = DP(3 - 1) + DP(3 - 2) + DP(3 - 3) // 3 - 1代表最后一次跳了1级台阶，3 - 2代表最后一次跳了2级台阶......
......
DP(n) = DP(n-1) + DP(n - 2) + DP(n - n)
DP(n-1) = DP(n - 2) + DP(n - 3) + DP(n - n)
上面两式相减，得：
DP(n) = 2 * DP(n - 1)
public class Solution {
public int JumpFloorII(int target) {
if (target == 1){
return target;
}
int f1 = 1;
int f2 = 2 * f1;
for(int i = 3; i <= target; i++) {
f2 += 2 * f1;
f1 = f2 / 2;
}
return f2;
}
}
查看5道真题和解析