algorithm - 动态规划 (DP) 中的重叠子问题是什么？

Question

要使动态规划适用，问题必须具有两个关键属性:最优子结构和 重叠子问题 [1] .对于这个问题，我们将只关注后一个属性。
有多种定义重叠子问题 ，其中两个是:

如果问题可以分解为多次重复使用的子问题，则称该问题具有重叠的子问题或 该问题的递归算法一遍又一遍地解决相同的子问题，而不是总是生成新的子问题 [2] .

要应用动态规划，优化问题必须具备的第二个要素是子问题的空间必须“小”，因为问题的递归算法一遍又一遍地解决相同的子问题，而不是总是生成新的子问题( CLRS 算法介绍)

如果找到解决方案涉及多次解决相同的子问题，那么这两个定义(以及互联网上的许多其他定义)似乎都可以归结为具有重叠子问题的问题。换句话说，在寻找原始问题的解决方案的过程中，有许多小的子问题被计算了很多次。一个经典的例子是斐波那契算法，很多例子都用来让人们理解这个属性。
直到几天前，生活还不错，直到我发现 Kadane 的算法让我质疑重叠子问题的定义 .这主要是因为人们对它是否是 DP 算法有不同的看法:

Dynamic programming aspect in Kadane's algorithm

Is Kadane's algorithm consider DP or not? And how to implement it recursively?

Is Kadane's Algorithm Greedy or Optimised DP?

Dynamic Programming vs Memoization (see my comment)

有人不认为 Kadane 算法是 DP 算法的最令人信服的原因是每个子问题只会 出现并计算一次 在递归实现中 [3] ，因此它不包含重叠的子问题属性。但是网上很多文章都认为Kadane的算法是DP算法，这让我怀疑我对什么的理解 重叠子问题首先意味着。
人们似乎在解读 重叠子问题属性 不同。使用简单的问题(例如斐波那契算法)很容易看到它，但是一旦您介绍了 Kadane 的算法，事情就会变得非常不清楚。如果有人能提供一些进一步的解释，我将不胜感激。

Answer 1

你已经阅读了很多关于这方面的内容。我唯一要补充的是:
Kadane 算法中的重叠子问题在这里:
max_subarray = max( 从 i=1 到 n [ max_subarray_to(i) ] )
max_subarray_to(i) = max( max_subarray_to(i-1) + array[i], array[i])
如您所见，对于每个 i，max_subarray_to() 被评估两次。 Kadane 的算法记住这些，把它从 O(n2) 变成 O(n)
......但正如@Stef 所说，你怎么称呼它并不重要，只要你理解它。