网站建设资讯

NEWS

网站建设资讯

每日算法之跳台阶

JZ69 跳台阶

描述

一只青蛙一次可以跳上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));
    }

}


当前名称:每日算法之跳台阶
文章分享:http://njwzjz.com/article/dsdihgo.html