题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法
一、递归实现：
这种方法最为低级，递归会产生大量的重复计算，耗费的时间是输入规模的指数级别的，可以加入计算缓存来提高递归速度。
public class Solution {
public int JumpFloor(int target) {
if(target <=0 ) return 0;
else if(target ==1 ) return 1;
else if(target ==2 ) return 2;
return JumpFloor(target-1)+JumpFloor(target-2);
}
}
显然，当我们需要求jumpFloor(5)的时候，会计算jumpFloor(3)和jumpFloor(4)，为了得到jumpFloor(3)我们会计算jumpFloor(2)和jumpfloor(1),同样的，为了得到jumpfloor(4)，又会计算jumpFloor(3)，jumpFloor(2)和jumpfloor(1)，这样就会有大量的重复计算产生。
为了避免这种重复计算，最为直接的想法就是将这些中间步骤的计算结果保存下来，再下一次使用时直接进行取用。
二、动态规划：
记忆性动态规划 【递归】
根据如上思路，我们将中间步骤的结果保存下来，形成了记忆性的动态规划。
自底向上，保留每一步的运行结果，留待后续的使用。
public class Solution {
public int JumpFloor(int target) {
if(target <=0 ) return 0;
if(target ==1 ) return 1;
int[] dp = new int[target+1]; //从0到n一共长n+1
dp[0]=0;
dp[1]=1;
dp[2]=2;
for(int i=3;i<=target;i++){
dp[i]=dp[i-1]+dp[i-2];
}
return dp[target];
}
}
这样节省了时间，但也并不是完美的，因为递归的计算每一步的结果并保存，必然需要大量的空间，故而这种算法的时间复杂度是O(N),空间复杂度也是O(n)，在使用大量堆栈的情况下，容易造成栈溢出。
故而我们考虑将递归转化为递推求解。从底层向上一步步递推求解，并且为了优化空间利用率，我们并不需要把中间每一步的结果都保存，只需要保存前两步的结果来计算该层的结果。
空间优化后的递推型动态规划
根据如上思路，代码为：
public class Solution {
public int JumpFloor(int target) {
if(target <=0 ) return 0;
if(target ==1 ) return 1;
if(target ==2 ) return 2;
int pre1 =1;
int pre2=2;
int result = 0;
for(int i=3;i<=target;i++){
result = pre1+pre2;
pre1=pre2;
pre2 = result;
}
return result;
}
}
转为为递推后，不需要保存所有的中间结果，额外空间的使用为常数个空间，故而这种方法下，时间复杂度为O(N)，而空间复杂度为O(1)。
小结：
使用动态规划的时候，一定要先确定一些边界值的状态，然后再求出递归或递推公式。
另外，做一道题目一定要将它想透彻，这样才能达到做题的目的。
