• 代码随想录算法训练营第三十二天 | 动态规划理论基础 509.斐波那契数 70.爬楼梯 746.使用最小花费爬楼梯


    动态规划理论基础:

    文章链接

    什么是动态规划:

    如果某一问题有很多重叠子问题,那么就适用于动态规划(Dynamic Programming简称DP)。
    动态规划每个状态是由上一个状态推导得到的,这就是与贪心的区别,贪心是局部直接选最优,与上一个状态没有关系

    动态规划解题步骤(※):

    五部曲:
    1.确定dp数组以及下标的含义
    2.确定递推公式
    3.dp数组如何初始化
    4.确定遍历顺序
    5.举例推导dp数组

    动态规划如何debug(※):

    ① 代码出现问题最好把dp数组打印出来,查看是否是按照自己的思路进行推导的。
    ② 如果打印出来和自己预先模拟推导是一样的,那么就是递推公式、初始化或者遍历顺序的问题;如果不一样,代码实现细节的问题==?==
    ③ 写代码前将状态转移在dp数组上的具体情况模拟一遍,确定最后推出的是想要的结果。然后再写代码。


    LeetCode 509.斐波那契数:

    文章链接
    题目链接:509.斐波那契数

    思路:

    动态规划五部曲:
    首先我们使用一维数组来保存递推的结果
    ① dp数组及下标含义:
    dp[i]的含义为:第 i 个数(i从0开始)的斐波那契数值为dp[i]
    ② 递推公式:

    dp[n] = dp[n - 1] + dp[n - 2] , n > 1
    

    ③ 如何初始化

    dp[0] = 0
    dp[1] = 1
    

    ④ 遍历顺序
    由递推公式dp[n] = dp[n - 1] + dp[n - 2]可知,dp[n]要用到dp[n - 1]和dp[n - 2]的信息,因此遍历顺序为从前往后。
    ⑤ 举例推导dp数组
    n = 5
    在这里插入图片描述

    class Solution:
        def fib(self, n: int) -> int:
            if n < 2:
                return n
            # 初始化dp数组
            dp = [0] * (n + 1)
            dp[1] = 1
            # 递推
            for i in range(2, n + 1):
                dp[i] = dp[i - 1] + dp[i - 2]
            return dp[n]
    

    时间复杂度:O(n)
    空间复杂度:O(n)
    实际上只需要维护两个数值,不需要记录整个序列

    class Solution:
        def fib(self, n: int) -> int:
            if n < 2:
                return n
            # 只需要用两个变量保存前面的数即可
            dp = [0, 1]
            for i in range(2, n + 1):
                sumDp = dp[0] + dp[1]
                dp[0] = dp[1]
                dp[1] = sumDp
            return dp[1]
    

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

    感悟:

    熟悉了动态规划五部曲。
    含义、递推、初始化、遍历顺序、举例


    LeetCode 70.爬楼梯:

    文章链接
    题目链接:70.爬楼梯

    思路:

    动态规划五部曲:
    本次我们还是使用一维数组保存递推结果
    ① dp数组及下标含义:
    dp[i]:表示上到第 i 阶台阶有dp[i]种方法
    ② 递推式:
    模拟几次就知道,上到第 i 阶台阶,既可以从第 i - 1阶上一步,也可以从第 i - 2阶上两步,因此上到第 i 阶台阶的方法数为上到第 i - 1阶的方法 + 上到第 i - 2阶的方法

    dp[i] = dp[i - 1] + dp[i - 2]
    

    ③ 如何初始化:
    dp[1] = 1,那么接下来是否需要初始化dp[0]
    1)按照题目意思解析dp[0]应当为0,因此呆在原地不动
    2)按照dp[2]来的话,dp[0]应当为1。
    但是题目中给出的n从1开始,dp[0]无意义。
    因此直接初始化为

    dp[1] = 1, dp[2] = 2
    

    ④ 遍历方式:
    根据递推式,dp[i]需要用到dp[i - 1]和dp[i - 2]的信息,因此是从前往后遍历
    ⑤ 举例推导
    n = 5
    在这里插入图片描述

    """
    正常使用dp数组
    """
    class Solution:
        def climbStairs(self, n: int) -> int:
            if n == 1:
                return 1
            # 初始化
            dp = [1] * (n + 1)
            dp[2] = 2
            for i in range(3, n + 1):
                dp[i] = dp[i - 1] + dp[i - 2]
            return dp[n]
    
    """
    简化,因为只用到了前面两个元素,因此只采用两个变量保存
    """
    class Solution:
        def climbStairs(self, n: int) -> int:
            if n == 1:
                return 1
            # 初始化
            dp = [0, 1, 2]
            for i in range(3, n + 1):
                sumDp = dp[1] + dp[2]
                dp[1] = dp[2]
                dp[2] = sumDp
            return dp[2]
    

    感悟:

    进一步熟悉了动态规划五部曲


    LeetCode 746.使用最小花费爬楼梯:

    文章链接
    题目链接:746.使用最小花费爬楼梯

    思路:

    从第 i - 1 阶台阶向上跳需要花费 cost[i - 1]
    动态规划五部曲
    还是使用一维数组记录递推的结果
    ① dp数组及下标含义:
    dp[i]:表示到达第 i 阶台阶的最低花费为dp[i]
    ② 递推式:
    到达第 i 阶台阶有两种:
    1)从第 i - 1 阶到达,花费为dp[i - 1] + cost[i - 1]
    2)从第 i - 2阶到达,花费为dp[i - 2] + cost[i - 2]
    因为要求最低花费,因此是两个求最小

    dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
    

    ③ 初始化
    能从下标为0或下标为1的台阶开始爬楼梯,而支付费用只是从楼梯向上爬,因此开始的第一步是不需要支付费用的。因此第一步的花费最低为0,即dp[0] = dp[1] = 0

    dp[0] = dp[1] = 0	# dp[i]是最低花费
    

    ④ 遍历顺序:
    dp[i]需要用到dp[i - 1]和dp[i - 2]的信息,因此遍历顺序为从前往后
    ⑤ 举例推导
    cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
    下图中的箭头表示dp[i]是由哪阶台阶跳过来的,其中红色的箭头表示最低花费的向上爬到楼顶的跳法
    在这里插入图片描述

    """
    正常使用dp数组
    """
    class Solution:
        def minCostClimbingStairs(self, cost: List[int]) -> int:
            n = len(cost)   # 楼顶
            dp = [0] * (n + 1)  # 初始化
            for i in range(2, n + 1):
                dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
            return dp[n]
            
    """
    实际上只需要用到两个变量记录即可
    """
    class Solution:
        def minCostClimbingStairs(self, cost: List[int]) -> int:
            # n = len(cost)   # 楼顶
            # dp = [0] * (n + 1)  # 初始化
            dp = [0, 0] # 默认第一步都是不花费体力的
            for i in range(2, len(cost) + 1):
                minDp = min(dp[0] + cost[i - 2], dp[1] + cost[i - 1])
                dp[0] = dp[1]
                dp[1] = minDp
            return dp[1]
            
    

    感悟:

    动态规划五部曲很好用


    学习收获:

    学习并实践了动态规划五部曲。
    今天动态规划的题目的递推式为斐波那契数的变形

  • 相关阅读:
    关于在Java中反转数组的4种详细方法
    SSM整合流程
    MybatisPlus 一些技巧
    DNS外带注入
    TDengine3.0流式计算引擎语法规则介绍
    pcba完整新工艺流程来了
    ElasticSearch中全文搜索(单词搜索、多次搜索、组合搜索和权重搜索)
    神经网络的优化器
    数仓项目拉链表
    Mac/Wins Matlab如何查看APPs源码
  • 原文地址:https://blog.csdn.net/decode12/article/details/143379914