变态跳台阶
变态跳台阶
http://www.nowcoder.com/questionTerminal/22243d016f6b47f2a6928b4313c85387
当target = 1 时,一种
1
当target = 2 时,二种
1,1
2
当target = 3 时,四种
最后一次跳3个台阶,前面有0个台阶未跳:1种
最后一次跳2个台阶,前面有1个台阶未跳:1种
最后一次跳1个台阶,前面有2个台阶未跳:2种
当target = n 时
最后一次跳n个台阶,前面有0个台阶未跳
最后一次跳n-1个台阶,前面有1个台阶未跳
最后一次跳n-2个台阶,前面有2个台阶未跳
......
最后一次跳2个台阶,前面有n-2个台阶未跳
最后一次跳1个台阶,前面有n-1个台阶未跳
由此推导出
sum = 1
j>=1 && j<target
sum = sum + JumpFloorII(j)
java代码如下:
public class Solution {
public int JumpFloorII(int target) {
if (target <= 2 && target >= 1){ return target; } int sum = 1; for (int i = 1; i < target; i++){ sum = sum + JumpFloorII(i); } return sum; }
}