剑指offer-跳台阶扩展问题题目描述算法思路代码实现

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。

输入：3
返回值：4

算法思路

由题可知：
f(n) = f(n-1)+f(n-2)+……f(1)
f(n-1) = f(n-2)+……f(1)
两式相减得：
f(n)=2f(n-1)
这就是递推公式

代码实现

递归

public class Solution {
    public int jumpFloorII(int target) {
        if(target==1){
            return 1;
        }
        return 2*jumpFloorII(target-1);
    }
}

时间复杂度：O(2ⁿ)
空间复杂度：递归栈的深度

动态规划

采用备忘录的形式对递归结果进行存储，并采取自底向上的方式遍历，就形成了动态规划。

public class Solution {
    public int jumpFloorII(int target) {
        int[] dp = new int[target+1];
        dp[1] = 1;
        for(int i=2;i<=target;i++){
            dp[i] = 2*dp[i-1];
        }
        return dp[target];
    }
}

时间复杂度：O(n)
空间复杂度：O(n)

动态规划优化

从递推公式 f(n)=2*f(n-1) 可以发现，当前项只与前一项有关，所以只需要存储前一项的值，而没有必要储存所有项的值，从而可以优化存储空间。

public class Solution {
    public int jumpFloorII(int target) {
        if(target==1){
            return 1;
        }
        int n=1;
        for(int i=2;i<=target;i++){
            n = 2*n;
        }
        return n;
    }
}

时间复杂度：O(n)
空间复杂度：O(1)

最后

以上就是纯情学姐为你收集整理的剑指offer-跳台阶扩展问题题目描述算法思路代码实现的全部内容，希望文章能够帮你解决剑指offer-跳台阶扩展问题题目描述算法思路代码实现所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。