算法套路十三——动态规划DP入门

这篇具有很好参考价值的文章主要介绍了算法套路十三——动态规划DP入门。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

算法套路十三——动态规划DP入门

动态规划和递归都是通过将大问题分解为较小的子问题来解决问题。它们都可以用来解决具有重叠子问题和最优子结构特性的问题。

  • 递归是一种自顶向下的方法,它从原始问题开始,递归地将问题分解为较小的子问题dfs(i)——dfs(i)代表的是从第i个状态开始进行递归求解能够得到的最终结果。直到子问题可以直接解决。递归可能会导致大量的重复计算,因为它没有记录已经解决的子问题的解对递归不理解的话可以前往算法套路七——二叉树递归进行学习
  • 动态规划是一种自底向上的方法,它从最小的子问题开始,逐步解决较大的子问题,直到解决原始问题。动态规划通过存储已经解决的子问题的解(通常使用表格或数组)来避免重复计算,从而提高了算法的效率。

因此,递归方法相对更加自然而直观,所以在很多情况下,动态规划算法的设计可以从递归算法开始,然后通过添加记忆化(Memoizatio n)技术来优化递归算法,之后对递归算法的代码进行自底向上的迭代改进,得到动态规划代码。

记忆化搜索介绍:https://oi-wiki.org/dp/memo/

算法示例:LeetCode198. 打家劫舍

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。算法套路十三——动态规划DP入门,# 算法套路,算法,动态规划,leetcode

递归

首先考虑直接用递归解决该题,
求偷窃到的最高金额,可以按照选或不选的思路,按照以下步骤:

  1. ans1记录不偷当前房屋的最大金额即dfs(i + 1)
  2. ans2记录偷当前房屋的最大金额即dfs(i + 2) + nums[i]
  3. 返回ans1与ans2的较大值
  4. 边界情况:当i>=len时表示无房屋可偷返回0
  5. 所求值: dfs(0)表示从第0个房屋开始偷窃能够获得的最大金额
class Solution:
    def rob(self, nums: List[int]) -> int:
        def dfs(i)-> int:
            if i >= len(nums):
                return 0
            # 不偷当前房屋
            ans1 = dfs(i + 1)
            # 偷当前房屋
            ans2 = dfs(i + 2) + nums[i]
            return max(ans1, ans2)
        return dfs(0)

按照上述的递归方式可以得到最大金额,但我们在LeetCode上会发现该方法超出时间限制。
算法套路十三——动态规划DP入门,# 算法套路,算法,动态规划,leetcode

如上图所示,我们对于选2这个分支计算了两次,那么如果房屋个数n更多,我们就会重复计算多次,这样会浪费大量的时间,故超出时间限制。

如果我们在第一次计算时,使用数组记录选择2的最大金额来保存计算结果,这样就可以避免重复计算,而这就是动态规划的精髓:递归搜索+保存计算结果=记忆化搜索。
算法套路十三——动态规划DP入门,# 算法套路,算法,动态规划,leetcode

递归+记忆化搜索

  1. 递归函数定义:dfs(i)函数表示从第i个房屋开始偷窃能够获得的最大金额
  2. 状态转移方程:ans1记录不偷当前房屋的最大金额即dfs(i + 1),ans2记录不偷当前房屋的最大金额即dfs(i + 2) + nums[i],dfs(i)为ans1与ans2的较大值即状态转移方程:dfs(i) =max (dfs(i - 1), dfs(i-2)+ nums[i])
  3. 边界条件:当i>=len时表示无房屋可偷返回0
  4. 所求值: dfs(0)表示从第0个房屋开始偷窃能够获得的最大金额。
class Solution:
    def rob(self, nums: List[int]) -> int:
    # python的@cache装饰器可以用来寄存函数对已处理参数的结果,以便遇到相同参数可以直接给出答案。
        @cache
        def dfs(i: int) -> int:
            if i >len(nums)-1: return 0
            return max(dfs(i + 1), dfs(i + 2) + nums[i])
        return dfs(0)

递归dfs()1:1 转换成迭代dp[]数组

如果一个动态规划问题可以用自底向上的方法求解,那么它通常可以从递归转换为迭代。
递归到迭代的转换是通过以下步骤实现的:

  1. 分析递归解法中的状态转移方程。在上述动态规划代码片段中,状态转移方程为:dfs(i) = max(dfs(i - 1), dfs(i - 2) + nums[i])
  2. 使用一个数组 dp[] 来存储子问题的解。数组的长度为len(nums) + 2,这是为了处理边界情况。
  3. 使用迭代的方式,自底向上计算子问题的解,如从前往后遍历数组,根据状态转移方程计算每个子问题的解,并将结果存储在数组中如本题我们可以通过 for i, x in enumerate(nums): dp[i + 2] = max(dp[i + 1],dp[i] + x)来迭代记录,与状态转移方程对比,我们可以发现改变的只将dfs全部换为了f[]数组记录,其次就是i的起始值会变化。
class Solution:
    def rob(self, nums: List[int]) -> int:
        dp = [0] * (len(nums) + 2)
        for i, x in enumerate(nums):
            dp[i + 2] = max(dp[i + 1], dp[i] + x)
        return dp[-1]

空间优化——滚动数组dp[i]转换为有限变量f0与f1

因为递推函数dp[i + 2] = max(dp[i + 1], dp[i] + x) 只依赖于前两个值dp[i + 1]和dp[i] + x),因此我们可以用f0与f1来循环记录中间结果。
当动态规划问题具有这种“滚动数组”特性时,通常可以通过使用有限数量的变量来减少空间复杂度。

class Solution:
    def rob(self, nums: List[int]) -> int:
        f0 = f1 = 0
        for i, x in enumerate(nums):
            f0, f1 = f1, max(f1, f0 + x)
        return f1

总结

如果不是很熟悉动态规划,在进行做题时可以采用示例的思路,首先思考只考虑递归该如何解决该题,之后1:1转换为迭代dp[]数组做动态规划,最后考虑是否可以进行空间优化。

算法练习一:LeetCode70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?算法套路十三——动态规划DP入门,# 算法套路,算法,动态规划,leetcode

递归+记忆化搜索

要求当前n层有多少种方法,每次可以走1或2台阶,即我们可以得出递推函数为dfs(i) =dfs(i - 1)+dfs(i-2),dfs(i)代表的是从第i个阶梯开始爬楼梯能够到达顶部的不同方法数。当 n 等于 1 或 2 时,直接返回 1 或 2。否则,递归调用 climbStairs(n-1) 和 climbStairs(n-2),并将它们的结果相加。

class Solution:
    @cache
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        elif n == 2:
            return 2
        else:
            return self.climbStairs(n-1) + self.climbStairs(n-2)

递归dfs()1:1 转换成迭代dp[]数组

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = [0] * (n + 2)
        dp[1] = 1
        dp[2] = 2
        for i in range(3, n+1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n]

空间优化——滚动数组dp[i]转换为有限变量f0与f1

由示例可知本题可以直接进行空间优化

func climbStairs(n int) int {
    if n==1{
        return 1
    }
    f0,f1:=1,2
    for i:=2;i<n;i++{
        f0,f1=f1,f0+f1
    }
    return f1
}

算法练习二:LeetCode213. 打家劫舍 II

你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组,计算你 在不触动警报装置的情况下 ,今晚能够偷窃到的最高金额。算法套路十三——动态规划DP入门,# 算法套路,算法,动态规划,leetcode

按照选或不选的思路分类讨论:文章来源地址https://www.toymoban.com/news/detail-608307.html

  • 如果选即偷nums[0],那么nums[1]和nums(n 一1]不能偷,问题变成从nums[2]到nums[n -2]的非环形版本,调用示例即198题的代码解决;
  • 如果不选即不偷nums(0],那么问题变成从naums[1]到numsn -1]的非环形版本,同样调用示例即198题的代码解决。
func rob1(nums []int, start, end int) int {
    f0, f1 := 0, 0
    for i := start; i < end; i++ {
        f0, f1 = f1, max(f1, f0+nums[i])
    }
    return f1
}

func rob(nums []int) int {
    n := len(nums)
    return max(nums[0]+rob1(nums, 2, n-1), rob1(nums, 1, n))
}
func max(a, b int) int { if b > a { return b }; return a }

到了这里,关于算法套路十三——动态规划DP入门的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【动态规划】LeetCode 312. 戳气球 --区间DP问题

      Halo,这里是Ppeua。平时主要更新C语言,C++,数据结构算法......感兴趣就关注我吧!你定不会失望。 🌈个人主页:主页链接 🌈算法专栏:专栏链接       我会一直往里填充内容哒! 🌈LeetCode专栏:专栏链接       目前在刷初级算法的LeetBook 。若每日一题当中有力所能

    2023年04月16日
    浏览(39)
  • 动态规划(DP)入门——线性DP

    在了解线性DP之前,我们首先要知道什么是动态规划,即为将一种复杂问题,分解成很多重叠的子问题,并通过子问题的解得到整个问题的解的算法。听起来比较抽象,动态规划简单来说就是确定问题的状态,通常题目都会提示,一般为“到第i个为止,xx为j(xx为k)的方案数/最

    2024年02月19日
    浏览(47)
  • DP算法:动态规划算法

    (1)确定初始状态 (2)确定转移矩阵,得到每个阶段的状态,由上一阶段推到出来 (3)确定边界条件。 蓝桥杯——印章(python实现) 使用dp记录状态,dp[i][j]表示买i张印章,凑齐j种印章的概率 i表示买的印章数,j表示凑齐的印章种数 情况一:如果ij,不可能凑齐印章,概

    2024年02月07日
    浏览(50)
  • 动态规划入门(DP)

    目录 1.DP概念和编程方法 1.1.DP概念 例如: 1.1.1.重叠子问题 1.1.2.最优子结构 “无后效性” 1.2.DP的两种编程方法 1.2.1.自顶向下与记忆化 1.2.2.自底向上与制表递推 对比两种方法 1.3.DP的设计和实现(0/1背包问题) 例题: Bone collector(hdu 2606) Problem Description Input Output Sample Inpu

    2024年02月19日
    浏览(37)
  • Leetcode动态规划篇(0-1背包问题一维和二维dp实现)

    🤗专栏:每日算法学习 💬个人主页:个人主页 🤓情况描述:有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大。每一件物品其实只有两个状态,取或者不取。

    2023年04月09日
    浏览(42)
  • 动态规划(DP)(算法笔记)

    本文内容基于《算法笔记》和官方配套练题网站“晴问算法”,是我作为小白的学习记录,如有错误还请体谅,可以留下您的宝贵意见,不胜感激。 动态规划(Dynamic Programming,DP)是一种用来解决一类最优化问题的算法思想。简单来说,动态规划将一个复杂的问题分解成若干个子

    2024年02月05日
    浏览(46)
  • ★动态规划(DP算法)详解

    什么是动态规划:动态规划_百度百科 内容太多了不作介绍,重点部分是无后效性,重叠子问题,最优子结构。 问S-P1和S-P2有多少种路径数,毫无疑问可以先从S开始深搜两次,S-P1和S-P2找出所有路径数,但是当这个图足够大,那就会超时。 动态规划旨在用 空间换时间 ,我们

    2024年02月04日
    浏览(49)
  • 算法——动态规划(DP)——递推

    动态规划常用于解决优化问题。 动态规划通常以自底向上或自顶向下的方式进行求解。 自底向上的动态规划从最简单的子问题开始,逐步解决更复杂的问题,直到达到原始问题。 自顶向下的动态规划则从原始问题出发,分解成子问题,并逐步求解这些子问题。 动态规划算法

    2024年01月20日
    浏览(56)
  • 【LeetCode动态规划#12】详解买卖股票I~IV,经典dp题型

    力扣题目链接(opens new window) 给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最

    2023年04月24日
    浏览(54)
  • C++动态规划-线性dp算法

    莫愁千里路 自有到来风 CSDN 请求进入专栏                                    X 是否进入《 C++ 专栏》? 确定 目录  线性dp简介 斐波那契数列模型  第N个泰波那契数 思路: 代码测试:  三步问题 思路: 代码测试: 最小花费爬楼梯 思路: 代码测试:  路径问题 数字三

    2024年02月19日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包