递归
- 设跳到n层的方法数为f(n),则f(n) = f(n - 1) + f(n - 2)
public class Solution { public int JumpFloor(int target) { if(target <= 1) return 1; return JumpFloor(target - 2) + JumpFloor(target - 1); } }
动态规划
- 设跳到n层的方法数为f(n),则f(n) = f(n - 1) + f(n - 2)
- 每次只需要使用到前两层方法数,所以只需要两个变量保存
public class Solution { public int JumpFloor(int target) { int first = 1, second = 1; // 超过两层就计算 while(target-- > 1) { // 当前层数等于前面一层跳法+前面两层跳法 second += first; first = second - first; } return second; } }