动态规划简介：重叠子问题和最优子结构

已发表: 2021-02-08

目录

介绍

假设我们有一个问题要解决 25 的平方。如果我们是第一次面对这个问题，那么我们可以手头或使用计算器来解决它。 但是如果我们之前已经看过这个问题或者之前已经解决了这个问题，那么我们有可能通过记住它来快速回答它。

这使我们得出结论，如果我们能记住它，那么我们下次可以跳过它。 动态编程的工作原理类似，其想法是记住计算结果并在将来需要时使用它。

这种简单的动态编程过程使其成为程序员征服高效代码之战的有力武器。

例如，让我们假设我们有一个复杂的问题，并且我们总是想一个将问题划分为子问题的解决方案。 但是我们可能会陷入多次计算子问题的情况。 在那里，我们使用动态规划来获得最佳解决方案。

动态规划有两个概念：

  1. 重叠子问题
  2. 最优子结构

重叠子问题

理解重叠子问题概念的一个经典例子是打印斐波那契数列的程序。

斐波那契数列的逻辑由“fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)”给出。 并且可以使用递归解决方案无缝执行此功能，基本情况为 fibonacci(0)=0 和 fibonacci(1)=1。

公共静态 int 斐波那契（int n）{
 如果(n== 0 || n== 1 )
 返回n;
 返回斐波那契(n -1 )+斐波那契(n -2 )；
 }
 公共静态无效主要（字符串[]参数）{
 System.out.print( “第四个斐波那契数是“ +fibonacci( 4 ));
 }

假设我们需要打印第 4 个斐波那契数字，那么递归树如下

斐波那契(4)

/ \

斐波那契 (3) + 斐波那契 (2)

/ \ / \

斐波那契 (2) + 斐波那契 (1) 斐波那契 (1) + 斐波那契 (0)

/ \

斐波那契 (1) + 斐波那契 (0)

请注意，斐波那契 (4) 是斐波那契数列中的第 5 位，因为我们从斐波那契 (0) 开始。 在上面的递归树中，我们可以看到 fibonacci(2) 重复了两次。 我们在高度为 4 的递归树中观察到重复，现在想象我们有一个巨大的递归调用，随后，将有一个高度很大的递归树。 并且会有很多这样的重复计算，称为重叠子问题。

我们有两种方法来处理这个（i）制表，（ii）记忆

让我们通过它们的实现来了解它们。

记忆

使用记忆法解决斐波那契问题可以如下图所示

静态 int[] 备忘录；
公共静态 int 斐波那契（int n）{
如果（备忘录[n]！=-1）
返回备忘录[n];
如果（n==0 || n==1）{
备忘录[n]=n;
返回 n;
}
备忘录[n] = 斐波那契(n-1)+斐波那契(n-2);
返回备忘录[n];
}
公共静态无效主要（字符串[]参数）{
备忘录=新的int [5]；
for(int i=0;i<=4;i++)
备忘录[i]=-1;
System.out.println("第4个斐波那契数是"+fibonacci(4));
}

在上面的代码中，我们正在创建一个维护日志文件或维护一个查找表并存储计算结果的值。 由于我们已经记住了所有计算值，如果需要，我们可以在将来使用它们，从而避免重复计算和重叠子问题。

所有逻辑都类似于递归解决方案，但我们所做的唯一区别是我们在将值返回给 main 方法之前将它们记录在 memo 数组中。 该算法的唯一限制是我们需要一个大小为 O(n) 的额外空间，但我们正在优化之前的递归解决方案。

制表

此方法与上述解决方案略有不同。 记忆遵循相同的递归解决方案。 但在制表中，我们遵循迭代解决方案。 它也被称为自下而上的方法。 让我们看一下自下而上方法的实现。

公共静态 int 斐波那契（int n）{
 整数表[]=新整数[n+ 1 ]；
 for (int i= 0 ;i<=n;i++){
 如果(i== 0 || i== 1 )
 表[i]=i;
 否则{
 表[i]=表[i -1 ]+表[i -2 ]；
 }
 }
 返回表[n]；
 }
 公共静态无效主要（字符串[]参数）{
 System.out.println( “第4个斐波那契数是“ +fibonacci( 4 ));
 }

我们知道 fibonacci(n)=fibonacci(n-1)+fibonacci(n-2)，在记忆中我们从 fibonacci(4) 函数调用开始，然后我们意识到我们还没有计算出它的值，所以我们'已经计算了它的值，然后存储它。

像 fibonacci(3)、fibonacci(2) 这样的进一步递归调用将面临类似的情况。 现在这使得很多递归调用在递归堆栈中等待，但无论如何我们都在跳过重叠子问题的重复。

我们还有一种方法可以迭代地计算从 0 到第 n 个元素的斐波那契，然后返回第 n 个斐波那契元素。 这就是我们在上面的代码中实现的。 此代码也具有相同的空间要求 O(n)。

结帐：成为全栈开发人员的技能

最优子结构

在这个概念中，只有最优地解决了相应的子问题，我们才能获得问题的最优解。

这个概念的一个经典例子是考虑图中节点之间的遍历。

让我们假设我们从 Telangana 到德里有多个根源。 如果我们有经过那格浦尔和瓜廖尔的最短路线。 那么从那格浦尔到德里德里的最短路线必须经过瓜廖尔。 现在我们可以将问题分解为子问题，即 Telangana 到那格浦尔、那格浦尔到 Gwalior、Gwalior 到德里。

这个属性的一个经典例子是两个字符串中最长的公共子序列。 子序列不同于子串。 在子序列中，字符不必在原始字符串中出现。

所以这个想法是通过优化解决它的子问题来解决它。 设 n 为最长公共子序列的长度。

如果 n=LCS(potato, tattoo)，则 n=LCS(potat,tatto)+1（如果最后一个字符相同），否则 n=maximum(LCS(potato,tatto), LCS(potat, tattoo)。

静态int lcs（字符串s1，字符串s2，int m，int n）{
 int dp[][] = 新的 int[m+ 1 ][n+ 1 ];
 for (int i= 0 ; i<=m; i++){
 对于(int j= 0 ; j<=n; j++){
 如果(i == 0 || j == 0 )
 dp[i][j] = 0 ;
 否则if (s1.charAt(i -1 ) == s2.charAt(j -1 ))
 dp[i][j] = dp[i -1 ][j -1 ]+ 1 ;
 别的
dp[i][j] = Math.max(dp[i -1 ][j], dp[i][j -1 ]);
 }
 }
 返回dp[m][n]；
 }
 公共静态无效主要（字符串[]参数）{
 System.out.println( “最长公共子序列的长度是“ +lcs( “potato” , “tattoo” , 6 , 6 ));
 }

在上面的代码中，我们使用制表方法实现了我们的逻辑，并计算了两个字符串中存在的最长公共子序列的长度。

另请阅读：印度的全栈开发人员薪水

从世界顶级大学在线学习软件开发课程。 获得行政 PG 课程、高级证书课程或硕士课程，以加快您的职业生涯。

结论

既然您知道使用其中一种强大的技术来征服高效代码的战斗，请尝试为其他问题实施动态编程，并开始增强您使用动态编程编写问题的能力。

总而言之，全栈开发人员课程是高技能的专家，他们可以处理与 Web 开发相关的所有事情。 这些全栈开发人员技能是他们与前端和后端开发人员的区别。

什么是动态规划？

计算机程序包含大量重复代码。 这是低效的，可能会影响其性能。 在这种情况下，使用动态规划。 动态规划是一种通过将复杂问题分解为更简单的子问题来解决复杂问题的方法，这些子问题中的每一个只解决一次，并使用表格存储它们的解决方案，然后在以后出现类似的子问题时查找这些表格复杂问题的解决方案。 动态规划算法用于解决运筹学、统计估计、模式识别、人工智能、机器学习、计算生物学等领域的各类优化问题。

什么是动态规划中的重叠子问题？

重叠子问题是当子问题具有在其他子问题中使用的解决方案时使用的概念。 这种重叠导致同一个子任务被多次解决。 问题是找到一种只解决子任务一次的方法，并使用该解决方案来获得其他子问题的解决方案。 动态规划算法使用记忆化解决了这个问题。 记忆是一种技术，我们存储子问题的解决方案，这样我们就不必再次解决它们。

动态规划中的最优子结构是什么？

最优子结构意味着问题的最优解与同一问题定义内较小问题的最优解相关。 最优子结构是解决问题或证明没有解决方案所需的附加要求。 通过最优子结构，我们可以证明许多问题 NP-hard。 解决DP问题的一般方法是使用动态规划矩阵来存储子问题的最优解。 动态规划矩阵可用于解决任何非零最优子结构 DP 问题。