如果您在该领域工作了很长时间，那么动态编程这个术语现在可能已经被广泛使用。 这个话题在设计评审会议和工程师的日常互动中经常出现，也是技术面试的焦点。 分而治之的策略是实现任何目标的万无一失的方法。 在计算机编程中，同样的想法也是如此。 许多困难都有子类型，可以将其隔离并单独处理，从而最终解决主要问题。 在这篇文章中，我们将讨论动态规划算法和Python。
什么是动态规划？
动态规划是一种解决复杂问题的方法，首先将复杂问题简化为更简单的问题，然后使用这些更简单问题的解决方案作为构建块来解决原始问题。
我们将手头的问题分成可管理的部分。 在大多数情况下，父母的问题和孩子的问题之间的唯一真正区别是它们的相对大小。 因此，这些小问题可以分解为更多的小问题，等等，无限地。 想象一下，一个问题及其各个子问题形成一棵树。 首先解决“叶子”问题，然后是“父”问题，依此类推。 当我们解决较小的困难时，我们会记录进度以供以后使用。 这使我们能够在将来跳过这部分问题。
该方法类似于分而治之的技术，它将问题分解为可以独立解决的较小问题，然后组合以获得最终解决方案。
动态规划如何工作？
动态规划之所以有效，是因为它通过将困难的问题分解为各个组成部分来简化它们。 下一步是找出应对这些随之而来的挑战的最佳答案。 这些过程的结果可以被记忆，以便可以从存储中检索并使用相应的解决方案，而无需进一步计算。 此外，还可以保存解决方案以避免重新计算以前解决的子问题。
存在两种完成动态规划的方法：
#1. 自上而下的方法
在计算机科学中，问题通常是通过递归地构建解决方案来解决的，或者通过使用先前步骤的结果来解决手头的问题。 如果子问题的解决方案相似，则可以记住或保留子问题解决方案的表格。 自上而下的方法基于死记硬背的学习。 记忆化与执行递归和缓存两次相同。 递归涉及对函数的间接调用，而缓存涉及跟踪中间结果。
自上而下方法的众多优点包括：
- 自上而下的方法易于掌握和应用。 为了更好地理解需要做什么，此方法将问题分解为其组成元素。 每一项新的发展都会消除以前无法克服的障碍。 其中一些甚至可能适用于其他问题。
- 它可以按需解决子问题。 自上而下的方法将允许将问题分解为可管理的块，并存储这些块的解决方案以供以后使用。 然后，客户可以寻求帮助来修复每个组件。
- 调试也得到简化。 将问题分成更小的部分可以更轻松地遵循答案并发现潜在的错误。
以下是使用自上而下方法的一些缺点：
- 自顶向下策略使用递归方法，与其他方法相比，该方法在调用堆栈中占用更多内存。 这最终会导致性能下降。 此外，如果递归回溯得太远，则可能会发生堆栈溢出。
#2. 自下而上的方法
在问题的解决方案以自身循环的方式以其子问题表达后，用户可以使用自下而上的方法重写问题，首先解决较小的子问题，然后将其解决方案应用于较大的子问题。
与自上而下的方法相反，使用自下而上的方法时消除了递归。 因此，递归函数不会增加不必要的开销或导致堆栈溢出。 此外，它还支持数据压缩。 通过消除重新计算相同值的需要，降低了递归的时间复杂性。
从头开始工作的一些好处如下：
- 它首先确定如何从较小的、可重用的子问题构建一个大问题。
- 通过消除递归，它有助于更好地利用可用内存。 其副作用是时序复杂度降低。
动态规划的特点
动态规划有两个显着特征：
#1. 子问题重叠
对主要问题进行更易于管理的修改称为“子问题”。 斐波那契数列，其中每个数字等于前两个数字的总和（0、1、1、2、3、5、8……）。 您可以将查找斐波那契数列中第 n 个值的任务划分为更易于管理的块。 当您通过一遍又一遍地解决相同的子问题来找到解决方案时，这些重叠的困难集变得越来越难以解决。
由于重叠子问题的普遍出现，动态编程可用于将大型编程作业划分为可管理的块。
#2. 下部结构具有最佳性能
当可以从所有子问题的解中创建最优解时，最优子结构的性质就会显现出来。 为了使递归发挥作用，您必须将从每次重叠中得出的答案应用于整个问题。 最优子结构属性由整个问题显示，就像斐波那契序列的情况一样，每个子问题都有一个解决方案，可以应用于序列中的下一个子问题以确定其值。
动态规划在现实世界中的应用
以下是动态规划的用途。
#1. 背包问题
动态规划已广泛用于解决背包问题。 这些是我们面临的问题：
每个子问题的理想值由相关物品的数量和背包中剩余的空间量决定，可以存储在二维数组中，从而快速解决该问题。 我们可以通过在每个阶段包含或排除当前项目来最大化价值。 答案可以在数组的右下角找到。
背包问题可用于多种情况，从打包行李到做出投资决策再到分配资源。
#2. 所有对最短路径
加权图中的最短路径问题是动态规划的另一个典型用途。 使用 Floyd-Warshall 或 Bellman-Ford 等技术，我们可以找到任意两个给定节点对之间的最短路径。
为了跟踪任意两个给定节点之间的最短路径，这些算法采用三维数组。 此外，为了跟踪它们距离起点有多远，他们将结果与每个阶段的起点和中间节点之间的距离进行比较。 迭代完成后，最终的解将是距离矩阵。
解决全对最短路径问题有多种用途，例如网络分析、路由、导航、社交网络分析等。
＃3。 缝雕
在图像处理领域，接缝雕刻是动态规划的一个有趣的应用。 当前的任务是减小图像的大小而不改变其任何基本特征。 图像中的低能量路线（称为接缝）可用于减去或添加像素以实现此效果。
使用动态编程，我们可以根据图像中每个像素的梯度和邻居来计算其累积能量，然后利用该信息来确定应该删除或添加哪些接缝。 然后，通过从图片底部向上，我们可以找到势能最小的接缝。 可以再次使用此方法，直到达到所需的尺寸。
此外，在接缝雕刻的帮助下，可以调整图像大小、裁剪、重新定位等。
＃4。 机器学习和基因组学
机器学习和基因组学挑战，如序列比对、隐马尔可夫模型和系统发育树，都适合动态编程的问题解决能力。
对齐多个符号序列（通常是 DNA 或蛋白质）以发现共性称为序列对齐。 这可以揭示它们的进化联系、社会功能或结构特征。 通过动态规划，可以通过为序列之间的匹配和不匹配分配分数来找到最佳比对。
称为隐马尔可夫模型的概率模型用于描述以未知状态为条件的时间序列数据。 它们对于对语音识别、自然语言处理、生物信息学等困难现象进行建模非常有用。当给定一组观察结果时，维特比和前向-后向等动态编程技术可以确定最可能的隐藏状态序列。
系统发育树显示了物种或基因之间随时间的联系。 从这些共同点中可以推断出共同的祖先、分歧的日期和进化事件。 此外，Fitch 和 Sankoff 等动态编程算法可用于使用测序数据生成最佳系统发育树。
#5。 密码学
密码学是对秘密通信的研究，也受益于动态规划的解决问题的能力。 加密、解密、数字签名、身份验证和其他类似过程都是密码学的一部分。
加密将信息从人类可读转换为密钥可读。 解密是使用原始密钥或新密钥将加密数据转换回明文的过程。 数字签名可以验证消息或文档的真实性和完整性。 检查发送者或接收者的凭证可以验证发送者或接收者的身份。
不同类型的密码学，包括动态密钥密码学、基于代码的密码学和基于动态编程的密码学，都可以通过动态编程来实现。
动态密钥加密是一种使用不断变化的密钥来加密和解密消息的机制。 “动态”的密钥是随着时间的推移或响应其他因素而演变的密钥。 这使得它们比容易受到攻击的静态密钥更安全。 在实现动态密钥加密时，可以使用动态编程来生成密钥并使密钥保持最新。
使用基于代码的加密技术，可以在加密和解密过程中使用纠错码来加密和解密消息。 可以使用纠错码来修复传输故障。 基于代码的密码学的使用被广泛认为是抗量子的，因为它可以抵御量子计算机的攻击。 动态编程可用于使用基于代码的密码系统对通信进行加密和解密。
作为一种加密和解密数据的方法，基于动态规划的密码学依赖于动态规划算法。 为了应对优化挑战，动态规划技术通常将问题划分为一组更简单的子问题。 动态规划密码学使用背包、最短路径和接缝雕刻。
什么是动态规划的真实示例？
现实世界的软件应用程序的许多实例都使用动态编程来保持敏捷性和效率，同时减少其在主机系统上的资源占用。 部分实例如下：
- 谷歌地图。 Google 地图使用动态编程来查找从给定起点到多个不同目的地的最快路线。
- 联网。 从单个发送者到多个接收者的顺序数据传输。
- 拼写检查器。 编辑距离算法确定将一个单词转换为另一个单词所需的步骤数，并提供两个单词之间不相似程度的定量测量。
- 抄袭软件。 文档距离方法有助于确定文本文档相似性。
- 搜索引擎。 确定两个互联网内容实际上有多相似。
如何解决动态规划问题？
了解动态规划概念后，下一步就是学习解决动态规划问题的公式。 以下是有关如何将动态规划应用于当前问题并得出可行解决方案的一些建议：
#1. 承认动态规划问题
最重要的部分是认识到动态规划算法可以解决指定的问题陈述。 解决这个问题需要首先确定每个问题陈述是否可以分解为更小的部分作为函数。
#2. 确定问题的原因
如果您已经得出结论，动态规划是完成这项工作的正确工具，那么下一步就是确定问题的组成子问题之间的递归结构。 在这种情况下，您必须考虑问题条件的流动性。 该变量可以是阵列位置或问题解决速度。
此外，计算问题的组成部分也至关重要。
＃3。 在迭代方法和递归方法之间进行选择
要解决动态编程问题，您可以利用迭代或递归方法。 从到目前为止所说的来看，可以肯定地说递归方法更可取。 然而，无论选择哪种方法来解决问题，所有上述考虑因素都是独立的。
递归和迭代方法都需要您指定递归关系和问题的基本情况。
＃4。 纳入记忆系统
在解决具有类似结构的问题时，回忆过去处理类似子问题的经验会很有帮助。 问题的时间复杂度将因此而降低。 如果我们在不使用记忆的情况下一遍又一遍地解决相同的子问题，任务的时间复杂度可能会呈指数级增长。
＃5。 将递归关系转化为文字
在解决问题时，许多程序员会跳过定义递归关系并直接跳到编码。 如果您可以在开始之前明确表达递归关系，您将更好地掌握问题并能够更快地编写代码。
算法动态规划
动态规划的大多数应用都包括递归算法。 使用动态规划进行优化意味着递归是大多数优化问题所固有的。
然而，动态规划不可能解决所有递归问题。 递归只能通过分而治之的策略找到解决方案，除非存在重叠的子问题，如斐波那契数列问题。
这是因为归并排序等递归算法中的底层子问题不重叠，从而排除了动态编程的使用。
不同类型的动态规划算法
以下是不同类型的动态规划算法。
#1. 最长公共子序列
最长公共子序列（LCS）的元素可以在原始序列中以任何顺序出现； LCS 被定义为所有指定序列共有的最长子序列。
如果提供两个序列S1和S2，则作为S1和S2两者的子序列的序列Z称为它们的公共子序列。 作为附加要求，Z 必须由集合 S1 和 S2 的索引的严格升序序列组成。
Z 中所选元素的索引必须严格递增才能形成上升序列。
#2. 弗洛伊德-沃歇尔算法
找到加权图中每对顶点之间的最短路径是 Floyd-Warshall 算法的目标。 此方法处理具有两个方向权重的图表。 另一方面，对于边的总和为负的循环，它会失败。
Floyd 算法、Roy-Floyd 算法、Roy-Warhshall 算法和 WFI 算法都是 Floyd-Warhshall 算法的名称。
该算法使用动态规划技术来定位最佳捷径。
动态规划算法如何比递归技术更快地解决 Lcs 问题？
动态编程减少了调用函数的开销。 它会记住每个函数调用的结果，以便后续调用可以使用存储的数据，而无需重复相同的工作。
每次将 X 的元素与 Y 的元素进行比较时，结果都会写入表中，以便可以在上述动态过程中的后续计算中使用。
因此，动态方法的运行时间与填充表所需的时间相同 (O(mn))。 相比之下，递归算法的复杂度为2max(m,n)。 另外，请阅读 如何根据您的业务需求选择正确的加密算法类型
Python 中的动态规划问题是什么
利用动态规划，人们可以针对任意数量的不同问题陈述确定最合适的解决方案。 接下来，我们将回顾一些最常被请求的著名问题陈述，并提供简短的解释以及相应的 Python 代码。
#1. 背包 (0-1) 有界
在这种情况下，给你 N 件商品的价格和重量，并要求你将它们装入容量为 W 的背包中； 目标是尽量减少选择的物品数量，同时仍将所有物品放入背包中。
大多数商品组织的技术面试都会要求应聘者解决背包问题，这是动态规划技术的典型示例。
问题陈述假设你有一个容量为W的袋子和一系列物品，每件物品都有重量和相应的利润。 目标是通过有效的不良填充来最大化收益。
答案是制作一个表格，其中列代表 1 到 W 之间的每个可能的权重，行代表您实际选择的权重。 该表将被称为 dp[][]。 如果“j”是背包的容量，并且包含重量/物品数组中的前“i”个元素，则表中的状态/cell dp[i][j]表示最高可能的利润。
因此，最终单元格中的值将表示解决方案。 只打包不超过背包重量限制的物品非常重要。 标准“weight>wt[i-1]”有两种替代方案，其中所有列都可以填充。
#2. 0/1 背包有限记忆
在袋子里装满已知重量和利润、尺寸为 K 的物品。您的目标是最大化您的收入。 在这里，我们将使用记忆而不是制表来看看是否可以解决问题。
上面的0/1背包问题采用自下而上的策略来发现解决方案，而本问题则采用基于记忆的自上而下的方法来获得解决方案。
动态编程使用记忆来减少多次解决问题的相同部分的需要。 这消除了不断解决子问题的需要，并简化了生成输出的过程。
问题陈述假设你有一个容量为W的袋子和一系列物品，每件物品都有重量和相应的利润。 如果以尽可能高的效率将袋子装满，则可以获得最高的潜在利润。
解决方案是首先构造一个二维数组来保存各个子问题的最终答案。 该表的列将列出 1 到 W 之间的所有潜在权重，并将其划分为多个部分，行将显示您在每个给定时间选择的权重。
我们使用 dp 数组来跟踪每个已解决的子问题。 我们不是解决先前解决的子问题，而是返回它的答案。
＃3。 等子集问题
使用动态规划找到给定集合的一个分区，使得两个子集中的项目总数相同，以解决相等子集问题。 除了它的其他名称之外，相等子集问题（或分区问题）是动态规划威力的最佳例证。
当前的任务要求我们将数组 arr 一分为二，以便随后的每个子集具有相同的总体大小。
作为解决方案，我们需要构建一个维度为 (sum/2+1)*(target+1) 的二维数组。 这里，可以为每个子集和每个总和存储分割原始数组的结果，并在以后检索。 数组的第一维将表示可以创建的各种子集，而数组的第二维将表示可以通过组合子集计算出的各种总和。
动态规划的优点
以下是动态规划的一些优点。
#1. 有效的补救措施
动态规划是一个强大的工具，用于寻找具有最佳子结构和重叠子问题的最佳解决方案。 通过将它们分解为可管理的部分，使用该方法可以更轻松地应对这些挑战。 动态规划能够通过避免重复计算和重用子问题的答案来创建最优解决方案。
#2. 便于轻松发现问题
通过首先将难题分解为更简单的部分，解决难题会变得更容易。 通过将复杂的问题划分为更易于管理的块，它使复杂的问题更容易解决。 此方法简化了解决方案并使问题更容易解决。
#3。 高效的
通过消除不必要的计算并回收以前解决的子问题，动态编程可以显着减少解决问题所需的时间。 当子问题重叠时，该方法可以通过减少解决问题所需的措施总数来提供帮助。
＃4。 当问题有多种解决方案时有效
动态规划可以帮助确定几种可能的解释中哪一种更有可能是这种情况。 当有多种可行的解决问题的选项时，此方法可以帮助我们将最佳选项归零。
动态规划的缺点是什么？
以下是动态规划的一些缺点。
#1. 不断重复出现的子问题
当问题具有重叠的子问题时，动态规划效果最好，但情况可能并非总是如此。 如果各个问题不交叉，它不会起作用，并且可能不会为您提供最佳解决方案。
#2. 时间和空间的复杂性
如果问题很大，动态规划可能需要大量的内存和存储空间，这会增加解决方案的时间和空间复杂度。 该方法使用存储器将中间结果存储在表或记忆表中。
＃3。 问题框架
尽管动态规划对于某些问题结构有效，但并不总是最佳选择。 当问题具有重叠的子问题时，此方法效果最佳，因此它可能不适用于其他情况。
＃4。 难以付诸实践
动态编程需要对算法和数据结构有深入的了解，这对于初学者来说实施起来具有挑战性。 该方法需要事先思考并深入熟悉当前的问题。
底线
总之，动态规划是寻找答案的有效方法，尽管其他方法更可取。 了解利弊并根据当前问题选择正确的方法至关重要。 对于具有最优子结构和子问题重叠的问题，动态规划可以产生最优解； 然而，这种方法可能并不总是适用。
尽管它开发起来很困难并且需要占用大量内存，但它简化问题解决过程和缩短计算时间的能力使其成为计算机科学家和数学家的重要资源。
动态规划常见问题解答
线性规划和动态规划有什么区别？
对于线性优化问题，我们有线性规划（LP）算法，对于具有非凸约束的一般非线性优化问题，我们有动态规划（DP），它保证了解的全局最优性。
学习动态规划有多难？
众所周知，动态规划是一门复杂的学科，特别是对于计算机科学领域的新手来说。 然而，只要牢牢掌握基本原理并进行大量实践，就可以轻松学习动态规划。
动态规划很难吗？
他们很难！ 首先，动态规划方法的思想可能很难掌握。 任何专家程序员都会证明，掌握 DP 需要投入大量时间。 将问题分解为各个组成部分并将其重新组装成一个可行整体的技能也是必要的。
类似文章
参考文献
