动态编程：特征，示例，优点，缺点 - 技术 - 2025

所述动态编程是一个模型的算法，解决了一个复杂的问题通过将它为子，储存其结果，以避免必须重新计算结果。

当您遇到可以分为相似子问题的问题时，可以使用此计划，以便可以重用它们的结果。在大多数情况下，此计划用于优化。

动态编程。斐波那契数列中叠加的子问题。资料来源：维基共享资源，en：用户：Dcoatzee，用户追踪：斯坦纳德/公共领域

在解决可用的子问题之前，动态算法将尝试检查先前解决的子问题的结果。子问题的解决方案相结合以获得最佳解决方案。

不必一遍又一遍地计算相同的子问题，而是可以在第一次遇到此子问题时将解决方案存储在某些内存中。当在另一个子问题的解决过程中再次出现该问题时，将采用已经存储在内存中的解决方案。

这是固定内存时间的好主意，在内存中使用额外的空间可以缩短找到解决方案所需的时间。

动态编程的特点

以下基本特征是应用动态编程之前必须要解决的问题：

最佳子结构

该特性表明，可以通过组合构成次要问题的最优解来解决最优化问题。这些最佳子结构通过递归描述。

例如，在图中，最优子结构将在从顶点s到顶点t的最短路径r中呈现：

即，在该最短路径r中，可以取任何中间顶点i。如果r确实是最短的路径，则可以将其划分为子路径r1（从s到i）和r2（从i到t），这样它们又是对应顶点之间的最短路径。

因此，要找到最短路径，可以轻松地递归地制定解决方案，这就是Floyd-Warshall算法的作用。

重叠子问题

子问题空间必须很小。也就是说，任何解决问题的递归算法都必须一次又一次地解决相同的子问题，而不是生成新的子问题。

例如，要生成斐波那契数列，我们可以考虑以下递归公式：Fn = F（n – 1）+ F（n – 2），以F1 = F2 = 1为基本情况。那么我们将得到：F33 = F32 + F31，并且F32 = F31 + F30。

如您所见，F31被解析为F33和F32的递归子树。尽管子问题的总数很少，但是如果您采用这样的递归解决方案，最终将一次又一次地解决相同的问题。

动态编程考虑了这一点，因此每个子问题只能解决一次。这可以通过两种方式完成：

自上而下的方法

如果可以使用子问题的解决方案来递归地提出任何问题的解决方案，并且如果这些子问题重叠，那么可以轻松地将子问题的解决方案存储或存储在表格中。

每次搜索新的子问题解决方案时，都会检查该表以查看以前是否已解决过。如果存储了解决方案，将使用它而不是再次计算。否则，将解决子问题，并将解决方案存储在表中。

自下而上的方法

在根据子问题递归提出问题的解决方案之后，可以尝试以向上的方式重新构造问题：首先，我们将尝试解决子问题，并使用其解决方案得出较大子问题的解决方案。

这通常也以表格形式完成，通过使用较小子问题的解决方案来迭代生成越来越大的子问题的解决方案。例如，如果已知F31和F30的值，则可以直接计算F32的值。

与其他技术的比较

可以通过动态编程解决的问题的一个重要特征是子问题应该重叠。这就是动态编程与分而治之技术的区别，在分治技术中，不需要存储最简单的值。

它与递归相似，因为在计算基本情况时，可以归纳确定最终值。当新值仅取决于先前计算的值时，这种自下而上的方法效果很好。

例

达到1的最小步骤

对于任何正整数“ e”，可以执行以下三个步骤中的任何一个。

-从数字中减去1。（e = e-1）。

-如果将其除以2，则将其除以2（如果e％2 == 0，则e = e / 2）。

-如果将其除以3，则将其除以3（如果e％3 == 0，则e = e / 3）。

根据上述步骤，应找到这些步骤的最小数目以使e达到1。例如：

-如果e = 1，结果：0。

-如果e = 4，结果：2（4/2 = 2/2 = 1）。

-当e = 7时，结果：3（7-1 = 6/3 = 2/2 = 1）。

焦点

可能会想到总是选择使n尽可能低的步长，并像这样一直持续到达到1。但是，可以看出，这种策略在这里行不通。

例如，如果e = 10，则步骤将为：10/2 = 5-1 = 4/2 = 2/2 = 1（4个步骤）。但是，最佳形式为：10-1 = 9/3 = 3/3 = 1（3步）。因此，必须尝试对找到的n的每个值执行所有可能的步骤，并选择这些可能性的最小数量。

一切都从递归开始：F（e）= 1 + min {F（e-1），F（e / 2），F（e / 3）}如果e> 1，则以基数为例：F（1） =0。有了递归方程，您就可以开始编码递归了。

但是，可以看出它具有重叠的子问题。此外，给定输入的最佳解决方案取决于其子问题的最佳解决方案。

如记忆中那样，所解决的子问题的解决方案将存储在此处以供以后使用。或者像在动态编程中一样，从底部开始，一直到给定的e。然后两个代码：

背诵

动态的自底向上编程

优点

使用动态编程的主要优点之一是，由于使用了先前计算的参考，因此它可以加快处理速度。由于它是一种递归编程技术，因此减少了程序中的代码行。

贪婪算法与动态编程

贪婪算法与动态编程相似，因为它们都是优化的工具。但是，贪婪算法会在每个局部步骤中寻找最佳解决方案。也就是说，它寻求贪婪的选择，以期找到全局最优值。

因此，贪婪算法可以做出一个假设，该假设在当时看起来是最优的，但是将来变得昂贵，并且不能保证全局最优。

另一方面，动态编程找到子问题的最佳解决方案，然后通过组合这些子问题的结果以实际找到最佳解决方案来做出明智的选择。

缺点

-需要大量内存来存储每个子问题的计算结果，而不能保证是否使用存储的值。

-很多时候，执行过程中以下子问题中都没有使用过输出值。这导致不必要的内存使用。

-在动态编程中，函数被递归调用。这样可以使堆栈内存不断增加。

递归与动态编程

如果您的内存有限，无法运行代码并且不关心处理速度，则可以使用递归。例如，如果您正在开发移动应用程序，则内存非常有限，无法运行该应用程序。

如果您希望程序运行更快并且没有内存限制，则最好使用动态编程。

应用领域

动态编程是解决问题的有效方法，否则，在合理的时间内很难解决这些问题。

从规划问题解决到语音识别，基于动态编程范例的算法已在许多科学领域中使用，包括人工智能中的许多示例。

基于动态规划的算法

动态编程非常有效，并且可以很好地解决各种问题。许多算法可以看作是贪婪算法的应用，例如：

-斐波那契数列。

-河内的塔楼。

-穿过弗洛伊德·沃绍尔（Floyd-Warshall）的所有较短路线。

-背包问题。

-项目进度。

-通过Dijkstra的最短方法。

-飞行控制和机器人控制。

-数学优化问题。

-分时：计划作业以最大化CPU使用率。

斐波那契数列

斐波那契数是按以下顺序找到的数字：0、1、1、2、3、5、8、13、21、34、55、89、144等

在数学术语中，斐波纳契数的序列Fn由递归公式定义：F（n）= F（n -1）+ F（n -2），其中F（0）= 0和F（ 1）= 1。

自上而下的方法

在此示例中，使用所有初始值的搜索数组初始化为-1。每当需要解决子问题时，都会首先搜索该搜索矩阵。

如果计算出的值在那里，则将返回该值。否则，将计算结果以存储在搜索数组中，以便以后可以重用。

自下而上的方法

在这种情况下，对于相同的斐波那契数列，首先计算f（0），然后计算f（1），f（2），f（3），依此类推。因此，子问题的解决方案是自下而上构建的。

参考文献

1. Vineet Choudhary（2020年）。动态编程简介。开发人员内部人员（Developer Insider），摘自：developerinsider.co。
2. 亚历克斯·艾伦（Alex Allain）（2020）。C ++中的动态编程。C编程。摘自：cprogramming.com。
3. After Academy（2020）。动态编程的想法。摘自：afteracademy.com。
4. Aniruddha Chaudhari（2019年）。动态编程和递归-差异，实例优势。CSE堆栈。摘自：csestack.org。
5. 代码厨师（2020）。动态编程教程。摘自：codechef.com。
6. 计划（2020）。动态编程。摘自：programiz.com。