为了使动态规划适用，问题必须具有两个关键属性：最优子结构 and 重叠子问题 [1] https://en.wikipedia.org/wiki/Dynamic_programming。对于这个问题，我们只关注后一个属性。
有各种不同的定义重叠子问题，其中两个是：
-
如果一个问题可以分解为多次重复使用的子问题，则称该问题具有重叠的子问题OR该问题的递归算法一遍又一遍地解决相同的子问题，而不是总是生成新的子问题 [2] https://en.wikipedia.org/wiki/Overlapping_subproblems.
-
应用动态规划的优化问题必须具备的第二个要素是子问题的空间必须“小”，因为问题的递归算法一遍又一遍地解决相同的子问题，而不是总是生成新的子问题 (算法简介由 CLRS 提供）
如果找到解决方案涉及多次解决相同的子问题，这两个定义（以及互联网上的许多其他定义）似乎都可以归结为具有重叠子问题的问题。换句话说，在寻找原问题的解的过程中，有许多小子问题被计算了很多次。一个典型的例子是斐波那契算法，很多例子都用来让人们理解这个属性。
直到几天前，生活还很美好，直到我发现Kadane 的算法让我质疑重叠子问题的定义。这主要是因为人们对于它是否是DP算法有不同的看法：
- Kadane 算法中的动态规划方面 https://stackoverflow.com/a/16324315/3385411
- Kadane的算法是否考虑DP？以及如何递归地实现呢？ https://www.quora.com/Is-Kadanes-algorithm-consider-DP-or-not-And-how-to-implement-it-recursively
- Kadane 的算法是贪婪算法还是优化 DP 算法？ https://stackoverflow.com/questions/31155269/is-kadanes-algorithm-greedy-or-optimised-dp
- 动态编程与记忆化（见我的评论） https://cs.stackexchange.com/a/99517/127532
有人不认为 Kadane 算法是 DP 算法的最令人信服的原因是每个子问题只会出现并计算一次在递归实现中[3] https://stackoverflow.com/a/16324315/3385411，因此它不涉及重叠子问题属性。然而，网上很多文章都认为Kadane的算法是DP算法，这让我质疑我对什么的理解重叠子问题意思是首先。
人们似乎这样解读重叠子问题性质不同。通过诸如斐波那契算法之类的简单问题很容易看出这一点，但一旦引入卡丹算法，事情就变得非常不清楚。如果有人能提供进一步的解释，我将非常感激。
您已经阅读了很多有关此内容的内容。我唯一要补充的是：
Kadane 算法中的重叠子问题如下：
max_subarray = max( 从 i=1 到 n [最大子数组到(i) ] )
max_subarray_to(i) = max(最大子数组到(i-1)+ 数组[i], 数组[i])
As you can see, max_subarray_to() is evaluated twice for each i. Kadane's algorithm memoizes these, turning it from O(n2) to O(n)
...但正如 @Stef 所说，只要你理解它，你叫它什么并不重要。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
