相关疑难解决方法(0)

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

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

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

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

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

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

有人不认为 Kadane 的算法是 DP 算法的最令人信服的原因是每个子问题只会在递归实现中出现和计算一次[3]，因此它不包含重叠子问题的属性。然而，互联网上的很多文章都认为 Kadane 的算法是一种 DP 算法，这让我怀疑我对重叠子问题的理解首先意味着什么。

人们似乎对重叠子问题的属性有不同的解释。使用简单的问题（例如斐波那契算法）很容易看到它，但是一旦您介绍了 Kadane 的算法，事情就会变得非常不清楚。如果有人能提供一些进一步的解释，我将不胜感激。