题目：
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
思路：
发波那契数列变形。
问题的解依赖子问题的解。同样用分治，或者bottom-up动态规划。
如果青蛙在第n级台阶上，那么它上一跳一定是在n-1, 或者n-2层台阶上。
假设f(n) 是跳n级台阶的所用跳法，那么 f(n) = f(n - 1) + f(n - 2)
base case:
f(1) = 1;
f(2) = 2;
代码：
1. 递归（不推荐）
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)
同样耗时长，但是这个思路和我一开始的思路重合，但是我卡在了递归的return上
public class Solution { // 把count 定义为全局变量 int count = 0; public int JumpFloor(int target) { jump(target); return count; } // 只计算所有跳法，在每一次递归的时候，不要返回值，只改变全局变量 public void jump(int target) { if (target == 1) { count++; return; } if (target == 2) {
// 两种跳法 +2 count = count + 2; return; } jump(target - 1); jump(target - 2); } }
2. bottom up (推荐)
public class Solution { public int JumpFloor(int target) { // 确保当target=1时， target[2]不越界，所以+2 int[] jumpTable = new int[target + 2]; jumpTable[1] = 1; jumpTable[2] = 2; for(int i = 3; i <= target; i++){ jumpTable[i] = jumpTable[i - 1] + jumpTable[i - 2]; } return jumpTable[target]; } }
时间复杂度：O(n)
原文：https://www.cnblogs.com/zyrJessie/p/12588350.html