动态规划(零)入门概念

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


前言

动态规划一直作为很重要的算法,其难度也一直让很多希望学动态规划的人望而却步。本篇文章将从动态规划的理论开始,从理念走向实战,带领大家去理解动态规划并且去用动态规划解决实际问题。

如果有不喜欢看文字性内容(太具有理论性)的或者已经学过动态规划的,可以跳过看动态规划系列的其他文章


一、动态规划算法的概念

动态规划的基本思想是将待求解问题分解成若干子问题,先求解问题,再结合这些子问题的解得到原问题的解。
适用于动态规划的求解的问题经分解得到的子问题往往不是互相独立的。

二、动态规划的设计步骤

教科书化的步骤如下所示:
(1) 找出最优解的性质,并刻画其结构特征;

(2) 递归地定义最优值;

(3) 以自底向上的方式计算出最优值;

(4) 根据计算最优值时得到的信息,构造最优解;

然而在实战中,可以换一种更加简洁明了的表达方式,即:
(1) 设计状态

(2) 写出状态转移方程

(3) 设定初始状态

(4) 执行状态转移

(5) 返回最终的解

三、动态规划算法的基本要素

动态规划算法的有效性依赖于问题本身所具有的两个重要性质:最优子结构性质子问题重叠性质

1、最优子结构

设计动态规划算法的第一步通常是要刻画最优解的结构。当问题的最优解包含了其子问题的最优解时,称该问题具有最优子结构性质。问题的最优子结构性质提供了该问题可用动态规划算法求解的重要线索。

在分析该问题的最优子结构性质时,所用的方法具有普遍性。首先假设由问题的最优解导出的其子问题的解不是最优的,再设法说明在这个假设下可构造出比原问题最优解更好的解,从而导致矛盾。

在动态规划算法中,利用问题的最优子结构性质,以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。算法考虑的子问题空间中规模较小。

2、重叠子问题

在用递归算法自顶向下解此问题时,每次产生的子问题并不总是新问题,有些子问题被反复计算。动态规划算法正是利用了这种子问题的重叠性质,对每个子问题只解一次,然后将其解保存在一个表格中,当再次需要解决此子问题时,只是简单地用常数时间查看一下结果。

3、备忘录方法

备忘录方法用表格保存已解决的子问题的答案,在下次需要解此子问题时,只要简单地查看该子问题的解答,而不必重新计算。与动态规划算法不同的是,备忘录方法的控制结构与直接递归方法的控制结构相同,区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看,避免了相同子问题的重复求解。


总结

本篇文章大多摘录自王晓东老师所编著的《计算机算法设计与分析》一书中,书中所讲述的都是偏向于理论性的内容,读者可以通过阅读,增添自己的理论知识,后面几篇文章将深入带领大家,去走入动态规划算法,领悟动态规划的奥妙。文章来源地址https://www.toymoban.com/news/detail-540631.html

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

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

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

相关文章

  • 数据结构与算法:动态规划(Dynamic Programming)详解

    动态规划(Dynamic Programming,简称DP) 是一种在数学、管理科学、计算机科学、经济学和生物信息学等领域中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划经常被用于求解优化问题。 动态规划的核心思想是将复杂问题分解为更小的子问

    2024年04月25日
    浏览(48)
  • 【夜深人静学数据结构与算法 | 第十篇】动态规划

    目录 前言: 动态规划: 常见应用: 解题步骤:  动态规划的简化步骤: 案例: 509. 斐波那契数 - 力扣(LeetCode) 70. 爬楼梯 - 力扣(LeetCode) 62. 不同路径 - 力扣(LeetCode) 总结:         本文我们将为大家讲解一下动态规划的理论知识,并且会讲解几道力扣的经典例题。

    2024年02月11日
    浏览(53)
  • python数据结构与算法-动态规划(最长公共子序列)

    一个序列的子序列是在该序列中删去若干元素后得 到的序列。 例如:\\\"ABCD”和“BDF”都是“ABCDEFG”的子序列。 最长公共子序列(LCS) 问题: 给定两个序列X和Y,求X和Y长度最大的公共子字列。 例:X=\\\"ABBCBDE”Y=\\\"DBBCDB”LCS(XY)=\\\"BBCD\\\" 应用场景:字符串相似度比对 (1)问题思考 思考: 暴

    2024年02月08日
    浏览(52)
  • ​Python—数据结构与算法​---动态规划—DP算法(Dynamic Programing)

    目录 我们一路奋战, 不是为了改变世界, 而是为了不让世界改变我们。 动态规划——DP算法(Dynamic Programing) 一、🏔斐波那契数列(递归VS动态规划) 1、🐒斐波那契数列——递归实现(python语言)——自顶向下 2、🐒斐波那契数列——动态规划实现(python语言)——自底

    2024年02月10日
    浏览(39)
  • 【数据结构与算法】Kadane‘s算法(动态规划、最大子数组和)

    Kadane\\\'s 算法是一种用于解决最大子数组和问题的动态规划算法。这类问题的目标是在给定整数数组中找到一个连续的子数组,使其元素之和最大(数组含有负数)。 算法的核心思想是通过迭代数组的每个元素,维护两个变量来跟踪局部最优解和全局最优解。 以下是Kadane’s算

    2024年03月22日
    浏览(102)
  • 【零基础】学python数据结构与算法笔记14-动态规划

    学习python数据结构与算法,学习常用的算法, b站学习链接 动态规划在基因测序、基因比对、hmm 有应用场景。 从斐波那契数列看动态规划 练习: 使用递归和非递归的方法来求解斐波那契数列。 这种非递归求斐波那契数,可以看成是一个动态规划思想,每次都会把重复子问

    2023年04月09日
    浏览(45)
  • 算法与数据结构(二十三)动态规划设计:最长递增子序列

    注:此文只在个人总结 labuladong 动态规划框架,仅限于学习交流,版权归原作者所有; 也许有读者看了前文 动态规划详解,学会了动态规划的套路:找到了问题的「状态」,明确了 dp 数组/函数的含义,定义了 base case;但是不知道如何确定「选择」,也就是找不到状态转移

    2024年02月13日
    浏览(43)
  • 【数据结构与算法】三个经典案例带你了解动态规划

    从表中我们可以看到,最大的公共子串长度为2,一共有两个长度为2的公共子串,分别是第一个字符串的第2个字符到第3个字符和第一个字符串的第3个字符到第4个字符,即 ba 和 ac 根据上面的方法,我们来用代码封装一下求取最大公共子串的函数 function publicStr(s1, s2) { // 创建

    2024年04月09日
    浏览(95)
  • 【地铁上的面试题】--基础部分--数据结构与算法--动态规划和贪心算法

    一、动态规划的基本概念和思想 1.1 动态规划的定义和特点 动态规划是一种解决多阶段决策问题的算法思想,它通过将问题划分为若干个子问题,并保存子问题的解来求解原问题的方法。动态规划的特点包括以下几个方面: 最优子结构性质:动态规划问题具有最优子结构,即

    2024年02月12日
    浏览(57)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包