为什么合并排序不是动态规划

Question

我读过这些话：

为了使动态规划适用，一个问题必须具有两个关键属性:最优子结构和重叠子问题。如果一个问题可以通过组合非重叠子问题的最优解来解决，那么这个策略就叫做“分而治之”。这也是为什么mergesort和quicksort没有被归类为动态规划问题的原因。

我有三个问题:

1. 为什么合并排序和快速排序不是动态编程？ 我认为合并排序也可以将小问题和小问题分开，然后做同样的事情等等。
2. Dijkstra算法是否使用动态算法？
3. 是否有使用动态规划的应用示例？

Answer 1

> < li>

要使动态编程适用于某个问题，应该有

i、 子问题中的最优结构：

这意味着当你把你的问题分解成更小的单元时，这些更小的单元也需要被分解成更小的单元以获得最优的解决方案。例如，在合并排序中，如果我们将一个数字数组分成两个子数组，对它们进行排序，然后将它们组合起来，就可以对它进行排序。对这两个子数组进行排序时，重复上一句中的相同过程。所以当我们找到它的子问题的最优解(我们对子数组进行排序并组合它们)时，就得到一个最优解(排序数组)。合并排序满足了这一要求。同样，子问题必须是独立的，才能遵循最优结构。这也可以通过合并排序来实现，因为子问题的解不会受到彼此解的影响。例如，数组的两个部分的解不受彼此排序的影响。

ii. 重叠的子问题：

这意味着在求解解决方案时，您制定的子问题会重复，因此只需要解决一次。在合并排序的情况下，在正常情况下很少满足此要求。像 2 1 3 4 9 4 2 1 3 1 9 4 这样的数字数组可能是合并排序的重叠子问题的良好候选者。在这种情况下，子问题 sort（2 1 3） 的解可以存储在一个表中以供重用，因为它将在计算过程中被调用两次。但正如你所看到的，随机数字数组具有这种重复设计的可能性非常小。因此，如果我们使用动态编程技术（如记忆）来执行合并排序等算法，则只会效率低下。

对Dijkstra的算法使用了@Alan在评论中提到的动态编程。链接

对如果我可以引用维基百科的话，“动态编程在生物信息学中被广泛用于序列比对、蛋白质折叠、RNA结构预测和蛋白质DNA结合等任务。”

1.https://en.wikipedia.org/wiki/Dynamic_programming

Answer 2

>

这里的关键词是“重叠子问题”和“最优子结构”。当您执行快速排序或合并排序时，您将递归地将数组分解为不重叠的较小部分。在任何给定的递归级别中，都不能对原始数组的相同元素进行两次操作。这意味着没有机会重复使用以前的计算。另一方面，许多问题确实涉及在重叠的子集上执行相同的计算，并且具有有用的特性，即在计算较大问题的最优解时，可以重复使用子问题的最优解决方案。

Dijkstra的算法是动态规划的一个经典示例，因为它重复使用先前的计算来发现两个节点a和Z之间的最短路径。假设a的近邻是B和C。我们可以通过将a和B之间的距离与计算出的从B到Z的最短路径相加来找到从a到Z的最佳路径；然后，从A到Z的最短路径将是这两条路径中的较短路径。这里的关键见解是，当计算长度为3的最短路径时，我们可以对长度为2的路径重复使用最短路径计算，以此类推。这样做会产生更高效的算法。

动态编程可用于解决许多类型的问题——有关一些示例，请参见http://en.wikipedia.org/wiki/Dynamic_programming#Examples：_Computer_algorithms。