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

Question

为了使动态规划适用，一个问题必须具有两个关键属性:最优子结构和重叠子问题[1]。对于这个问题，我们将只关注后一个属性。

重叠子问题有多种定义，其中两个是：

• 如果一个问题可以分解为多次重用的子问题，或者问题的递归算法一遍又一遍地解决同一个子问题，而不是总是产生新的子问题，那么问题就被称为具有重叠的子问题[2]。
• 要应用动态规划，优化问题必须具备的第二个要素是子问题的空间必须“小”，因为问题的递归算法一遍又一遍地解决相同的子问题，而不是总是生成新的子问题（CLRS 算法简介）

如果找到解决方案涉及多次解决相同的子问题，那么这两种定义（以及互联网上的许多其他定义）似乎都可以归结为一个具有重叠子问题的问题。换言之，有许多小的子问题，在寻找原始问题的解的过程中要多次计算。一个经典的例子是斐波那契算法，很多例子都用它来让人们理解这个特性。

直到几天前，生活还很好，直到我发现了Kadane的算法，这让我质疑重叠的子问题定义。这主要是因为人们对它是否是 DP 算法有不同的看法：

• Kadane算法中的动态规划方面
• Kadane的算法是否考虑DP？以及如何递归实现？
• Kadane的算法是贪婪的还是优化的DP？
• 动态编程vs记忆（见我的评论）

有人不认为 Kadane 算法是 DP 算法的最令人信服的原因是，每个子问题只会在递归实现中出现并计算一次 [3]，因此它不需要重叠的子问题属性。然而，互联网上的许多文章认为 Kadane 的算法是一种 DP 算法，这让我质疑我对重叠子问题的理解。

人们似乎对重叠子问题的性质有不同的解释。对于像斐波纳契算法这样的简单问题，很容易看到它，但是一旦你引入卡丹算法，事情就变得非常不清楚了。如果有人能提供一些进一步的解释，我将不胜感激。

Answer 1

你已经读了很多了。我唯一要补充的是：

卡丹算法中的重叠子问题如下：

max_subarray = max(从i=1到n [ max_subarray_to(i) ])

max_subarray_to（i） = max（max_subarray_to（i-1） 数组[i]， 数组[i]）

如您所见，对于每个i，max_subarray_to（）被求值两次。卡丹的算法会记住这些，将其从O（n²）转换为O（n）

...但就像@Stef说的，你叫什么都不重要，只要你懂就好。