JZ8 跳台阶
（简单）
题目
描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
示例1
输入：
2
返回值：
2
示例2
输入：
7
返回值：
21
思路
1 方法一：递归
此题可转换为为斐波那契数列问题，由于只能一次跳 1 级或一次跳 2 级台阶，因此第 n 级台阶一定是从 n-1 级台阶或 n-2 级台阶跳上去的，所以若想要求 n 级台阶有几种跳法，可以抽象成为 n-1 级台阶和 n-2 级台阶的跳法之和，因此得到公式 F[n] = F[n - 1] + F[n - 2] ，而假设有第 0 级台阶，另 F[0] = 1，而 F[1] 本身就该为 1，因此，F[0] = F[1] = 1，这样求出的 F[2]，F[3]，…，经验证都是正确的，因此将此题成功转为斐波那契数列问题。
时间复杂度：O(2^n)
空间复杂度：递归栈的空间
【实现】
public class Solution {
//方法一：递归
public int jumpFloor(int target) {
if (target <= 1) {
return 1;
}
return jumpFloor(target - 1) + jumpFloor(target - 2);
}
}
2 方法二：递归优化—记忆化搜索
在方法一的直接递归调用中，进行了大量重复的递归计算，例如在计算 jumpFloor(7) 时，进行了 jumpFloor(6) 和 jumpFloor(5) 的入栈，而在计算 jumpFloor(6) 时，又出现了 jumpFloor(5) 的入栈，因此有进行了一次 jumpFloor(5) 的计算，而在之后又有了许多类似的重复递归入栈操作，大大影响的时间效率，因此，我们可以利用一个暂存的数组，来对当前递归出的 jumpFloor(i) 进行记录，从而在之后递归时，先检验是否有 jumpFloor(i) 的值，有则不必再进行计算，这样就大大提高了算法的效率。
时间复杂度：O（n）， 没有重复的计算
空间复杂度：O（n）和递归栈的空间
public class Solution {
//方法二：递归优化—记忆化搜索
private int[] temp = new int[100];
public int jumpFloor(int target) {
if (target <= 1) {
return 1;
}
if (temp[target] != 0) {
return temp[target];
}
return temp[target] = jumpFloor(target - 1) + jumpFloor(target - 2);
}
}
可见，运行时间较之前缩短了十几倍
3 方法三：动态规划
其实做来做去，这个跳台阶问题，其实就是求斐波那契数列的问题，如果想让方法二继续优化，那就用动态规划，优化掉递归栈空间。方法二是从上往下递归的然后再从下往上回溯的，最后回溯的时候来合并子树从而求得答案。那么动态规划不同的是，不用递归的过程，直接从子问题向最终问题求得答案。过程是从下往上。
时间复杂度：O（n）
空间复杂度：O（1）
补充：
能采用动态规划求解的问题的一般要具有3个性质：
(1) 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
(2) 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
（3）有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势。
public class Solution {
//方法三：动态规划
public int jumpFloor(int target) {
int a = 1;
int b = 1;
int t = 0;
for (int i = 2; i <= target; i++) {
t = b;
b = a + b;
a = t;
}
return b;
}
}
JZ9 跳台阶扩展问题
（简单）
题目
描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。
示例
输入：
3
返回值：
4
思路
方法一：暴力解法
由于第 n 级台阶的跳法，就是第 1 级台阶的跳法 + 第 2 级台阶的跳法 + … + 第 n -1 级台阶的跳法 + 1（这个 + 1 其实可以抽象地理解为，一次性跳至 n 级台阶的1次，而如果当前处于 n - 1 级台阶，则下此必定是再跳 1 次即可，因此就是默认情况，这个 1 次不用再加上，加上就重复了），因此，可以得出规律，f[n] = f[n-1] + f[n-2] + … + f[0]（f[0] = 1，f[1] = 1），
【实现】
public class Solution2 {
//方法一：暴力解法
//借助规律 f[n] = f[n-1] + f[n-2] + ... + f[0]
public int jumpFloorII(int target) {
int[] F = new int[target + 1];
F[0] = 1;
F[1] = 1;
for (int i = 2; i <= target; i++) {
for (int j = 0; j < i; j++) {
F[i] += F[j];
}
}
return F[target];
}
}
方法二、三、四：递推—得出巧妙规律
对于方法一中的：f[n] = f[n-1] + f[n-2] + … + f[0]
那么f[n-1] 为多少呢？
f[n-1] = f[n-2] + f[n-3] + … + f[0]
所以一合并，得出规律 f[n] = 2*f[n-1]，初始条件f[0] = f[1] = 1，因此，接下来便可采用方法二：递归，方法三：记忆化递归，方法四：动态规划的方法实现，这种方法十分巧妙，我是在看了题解后才知道的，方法十分简单，但确实我是没有想到，同时我也在这道题中感受到了数学的魅力。
由于递归、记忆化递归、动态规划三种方式的实现，和初级版的跳台阶问题十分类似，因此我不再一一实现，但为了于暴力解法进行效率的比对，我这里采用动态规划的方式实现一下：
【实现】
public class Solution2 {
//方法四：动态规划
int result = 1;
for (int i = 2; i <= target; i++) {
result *= 2;
}
return result;
}
