跳台阶跳台阶

题目描述
一只青蛙一次可以跳上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)。
小结：使用动态规划的时候，一定要先确定一些边界值的状态，然后再求出递归或递推公式。
另外，做一道题目一定要将它想透彻，这样才能达到做题的目的。