变态跳台阶多种解法
变态跳台阶
http://www.nowcoder.com/questionTerminal/22243d016f6b47f2a6928b4313c85387
普通人能想到的暴力解法:
跳上第n个台阶,我们可以推算上一步是如何跳到这第n个台阶的:如果上一步跳 1 步到达第 n 个台阶,说明上一步在第 n-1 个台阶。已知跳到第n-1个台阶的方法数为f[n-1]
如果上一步跳 2 步到达第 n 个台阶,说明上一步在第 n-2 个台阶。已知跳到第n-2个台阶的方法数为f[n-2]
如果上一步跳 n 步到达第 n 个台阶,说明上一步在第 0 个台阶。已知跳到 第0个台阶的方法数为f[0]
那么总的方法数就是所有可能的和。也就是f[n] = f[n-1] + f[n-2] + ... + f[0]
显然初始条件f[0] = f[1] = 1
所以我们就可以先求f[2],然后f[3]...f[n-1], 最后f[n]
public class Solution { public int JumpFloorII(int target) { if(target == 0 || target == 1) return 1; int[] f = new int[target+1]; f[0] = f[1] = 1; for(int i = 2; i <= target; i++){ for(int j = 0; j < i; j++){ f[i] += f[j]; } } return f[target]; } }
时间复杂度 O(N2)
空间复杂度 O(N)
- 我们可以发现规律
f(1) = f(0) = 1;
f(2) = f(1) + f(0) = 2 * f(1);
f(3) = f(2) + f(1) + f(0) = 2 * f(2);
f(4) = 2* f(3)
...
f(n) = 2 * f(n-1)
因为初始f(1)为1,所以刚好可以利用位运算。public class Solution { public int JumpFloorII(int target) { return 1 << (target - 1); //左移1位是乘2,左移几就是几次乘2 } }
时间复杂度 O(1)
空间复杂度 O(1)
基于该思想还有别的方法能够降低复杂度
public class Solution { public int JumpFloorII(int target) { if(target == 0 || target == 1) return 1; int a = 1, b = 0; for(int i = 2; i <= target; i++){ b = a << 1; a = b; } return b; } }
时间复杂度 O(n)
空间复杂度 O(1)
只有1级和2级台阶的解法:
可以使用递归:
public class Solution { public int JumpFloor(int target) { if(target == 1) return 1; if(target == 2) return 2; return JumpFloor(target-1) + JumpFloor(target-2); } }
但是时间复杂度为 O(2的n次方)
因此在面试时还是推荐递推型:
public class Solution { public int JumpFloor(int target) { int a = 1, b = 1; for(int i = 1; i < target; i++){ //a是n后返1个的台阶 a = a + b; //b是n后返2个的台阶 b = a - b; } return a; } }