剑指offer(C++)-JZ69:跳台阶(算法-动态规划)

简介: 剑指offer(C++)-JZ69:跳台阶(算法-动态规划)

题目描述:

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

数据范围:1≤n≤40

要求:时间复杂度:O(n) ,空间复杂度: O(1)

示例:

输入:

2


返回值:

2


说明:

青蛙要跳上两级台阶有两种跳法,分别是:先跳一级,再跳一级或者直接跳两级。因此答案为2

解题思路:

本题考察算法-动态规划算法的使用。用四种逐优的解法,来一步步发现动态规划算法的优势。


解法一:递归法。青蛙可以一次跳一阶也可以跳两阶,假设跳到n阶时的方案数为F(n),那么跳到n-1阶的方案数再加一就能跳到n阶,跳到n-2阶的方案数再加二也能跳到n阶,则跳到n阶的方案数是它们的和,即F(n)=F(n-1)+F(n-2),初始条件n小于等于1时,方案数为1,用递归很容易实现。时间复杂度O(2^n),因为每次调用jumpFloor,都要继续调用两次jumpFloor,这个复杂度是很高的;空间复杂度是递归栈空间,递归次数很大时,空间复杂度也是很高的。该方法虽然很容易写且理解,但是最不实用。


解法二:改进递归法。在解法一中不难发现,jumpFloor在执行过程中进行了大量的重复工作,比如计算F(5)时计算过F(4)和F(3),但计算F(6)时又计算了多遍,那如果用数组存好F(x)的数值,只要计算一次就足够了,再次调用只需要读取数组数据即可。这样时间复杂度降到了O(n),空间复杂度变为O(n)和递归栈空间。


解法三:动态规划。动态规划是在计算过程中,不断分析每一步的最优解,当进行到最后一步时,结果自然得出。如果说递归法是从后往前,那么动态规划就是从前往后。节省了递归栈空间。本题目简单,用一个循环即可完成,时间复杂度和空间复杂度均为O(n)。


解法四:改进的动态规划。解法三中空间复杂度还是太高,考虑到我们只需要求最终的结果,所以中间过程的数据并不需要保存下来,那么可以优化掉数组,用变量来动态存储F(n-1)和F(n-2)即可,时间复杂度为O(n),空间复杂度为O(1)。

测试代码:

解法一:递归法

class Solution {
  public:
    int jumpFloor(int number) {
        if (number <= 1)
            return 1;
        return jumpFloor(number-1)+jumpFloor(number-2);
    }
};

解法二:改进递归法

class Solution {
  public:
    int data[100]{0};
    int jumpFloor(int number) {
        if (number <= 1)
            return 1;
        if(data[number]>0)
            return data[number];
        else
            data[number]=jumpFloor(number-1)+jumpFloor(number-2);
        return data[number];
    }
};

解法三:动态规划

class Solution {
  public:
    int data[100]{0};
    int jumpFloor(int number) {
        data[0]=1;
        data[1]=1;
        for(int i=2;i<=number;++i)
            data[i]=data[i-1]+data[i-2];
        return data[number];
    }
};

解法四:改进的动态规划

class Solution {
  public:
    int jumpFloor(int number) {
        int a=1,b=1,c=1;
        for(int i=2;i<=number;++i)
        {
            c=a+b;
            a=b;
            b=c;
        }
        return c;
    }
};


相关文章
|
9天前
|
算法 Python
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果;贪心算法在每一步选择局部最优解,追求全局最优;动态规划通过保存子问题的解,避免重复计算,确保全局最优。这三种算法各具特色,适用于不同类型的问题,合理选择能显著提升编程效率。
26 2
|
1月前
|
算法
动态规划算法学习三:0-1背包问题
这篇文章是关于0-1背包问题的动态规划算法详解,包括问题描述、解决步骤、最优子结构性质、状态表示和递推方程、算法设计与分析、计算最优值、算法实现以及对算法缺点的思考。
65 2
动态规划算法学习三:0-1背包问题
|
1月前
|
算法
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
这篇文章介绍了动态规划算法中解决最大上升子序列问题(LIS)的方法,包括问题的描述、动态规划的步骤、状态表示、递推方程、计算最优值以及优化方法,如非动态规划的二分法。
65 0
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
|
1月前
|
算法
动态规划算法学习二:最长公共子序列
这篇文章介绍了如何使用动态规划算法解决最长公共子序列(LCS)问题,包括问题描述、最优子结构性质、状态表示、状态递归方程、计算最优值的方法,以及具体的代码实现。
118 0
动态规划算法学习二:最长公共子序列
|
1月前
|
存储 算法 C++
高精度算法(加、减、乘、除,使用c++实现)
高精度算法(加、减、乘、除,使用c++实现)
420 0
高精度算法(加、减、乘、除,使用c++实现)
|
1月前
|
算法 数据处理 C++
c++ STL划分算法;partition()、partition_copy()、stable_partition()、partition_point()详解
这些算法是C++ STL中处理和组织数据的强大工具,能够高效地实现复杂的数据处理逻辑。理解它们的差异和应用场景,将有助于编写更加高效和清晰的C++代码。
22 0
|
1月前
|
存储 算法
动态规划算法学习一:DP的重要知识点、矩阵连乘算法
这篇文章是关于动态规划算法中矩阵连乘问题的详解,包括问题描述、最优子结构、重叠子问题、递归方法、备忘录方法和动态规划算法设计的步骤。
101 0
|
1月前
|
存储 算法 决策智能
【算法】博弈论(C/C++)
【算法】博弈论(C/C++)
|
1月前
|
存储 算法 C++
【算法】哈希映射(C/C++)
【算法】哈希映射(C/C++)
|
1月前
|
机器学习/深度学习 人工智能 算法
【算法】最长公共子序列(C/C++)
【算法】最长公共子序列(C/C++)