剑指offer27 JZ69 跳台阶

递归

思路

• 方法一：递归 题目分析，假设f[i]表示在第i个台阶上可能的方法数。逆向思维。如果我从第n个台阶进行下台阶，下一步有2中可能，一种走到第n-1个台阶，一种是走到第n-2个台阶。所以f[n] = f[n-1] + f[n-2]. 那么初始条件了，f[0] = f[1] = 1。 所以就变成了：f[n] = f[n-1] + f[n-2], 初始值f[0]=1, f[1]=1，目标求f[n] 看到公式很亲切，代码秒秒钟写完。

public class Solution {
    public int jumpFloor(int target) {
        if(target<=1){
            return 1;
        }
        else{
            //走到第n 阶台阶有 n-1 中跳法和n-2 的跳法， f(n)=f(n-1)+f(n-2)
            return jumpFloor(target-1)+jumpFloor(target-2);
        }

    }
}

动态规划

思路

• 虽然方法二可以解决此题了，但是如果想让空间继续优化，那就用动态规划，优化掉递归栈空间。 方法二是从上往下递归的然后再从下往上回溯的，最后回溯的时候来合并子树从而求得答案。 那么动态规划不同的是，不用递归的过程，直接从子树求得答案。过程是从下往上。

public class Solution {

    public int jumpFloor(int target) {
        int[] dp =new int[50] ;
        dp[1]=1;dp[0]=1;
      for(int i=2;i<dp.length;i++){
          dp[i]=dp[i-1]+dp[i-2];
      }
        return dp[target];

    }
}