每日算法之跳台阶

描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。


数据范围：1 \leq n \leq 401≤n≤40
要求：时间复杂度：O(n)O(n) ，空间复杂度： O(1)O(1)

方法1 递归

思路

题目分析，假设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

代码

if(target == 0 || target == 1) return 1;
        return jumpFloor(target - 1) + jumpFloor(target - 2);

方法2 递归改进

思路

f(2)计算了两次，f(1)计算了3次，f(0)计算了2次。可以采用一个数组存储已经被计算过的值

此方法编译不通过，空间复杂度过高

代码

int[] f = new int[50];
        if (target <= 1) return 1;
        if (f[target] != 0) return f[target];
        return f[target] = (jumpFloor(target - 1) + jumpFloor(target - 2));

方法3 动态规划

思路

思路：既然与斐波那契数列相同，我们就把它放入数组中来解决。


具体做法：

  step 1：创建一个长度为n+1的数组，因为只有n+1才能有下标第n项，我们用它记录前n项斐波那契数列。

  step 2：根据公式，初始化第0项和第1项。

  step 3：遍历数组，依照公式某一项等于前两项之和，将数组后续元素补齐，即可得到fib[n]fib[n]fib[n]

代码

package esay.JZ69跳台阶;

public class Solution {
    public static int jumpFloor(int target) {
        //方法1
        /*if(target == 0 || target == 1) return 1;
        return jumpFloor(target - 1) + jumpFloor(target - 2);*/

        //方法2
        /*int[] f = new int[50];
        if (target <= 1) return 1;
        if (f[target] != 0) return f[target];
        return f[target] = (jumpFloor(target - 1) + jumpFloor(target - 2));*/

        //方法3
        if (target <= 1)
            return 1;
        int[] temp = new int[target + 1];
        //初始化
        temp[0] = 1;
        temp[1] = 1;
        //遍历相加
        for (int i = 2; i <= target; i++)
            temp[i] = temp[i - 1] + temp[i - 2];
        return temp[target];

    }

    public static void main(String[] args) {
        System.out.println(jumpFloor(37));
    }

}