什么是动态规划 (DP) 中的重叠子问题？
What are overlapping subproblems in Dynamic Programming (DP)?
要使动态规划适用，问题必须具备两个关键属性：最优子结构和重叠子问题[1]。对于这个问题，我们只关注后者属性。
重叠子问题有多种定义，其中两个是：
- 如果问题可以分解为可多次重复使用的子问题，则称该问题具有重叠子问题或问题的递归算法解决同一个子问题一遍又一遍，而不是总是产生新的子问题 [2].
- 要应用动态规划，优化问题必须具备的第二个要素是 space 子问题必须“小”，因为该问题的递归算法可以求解一遍又一遍地解决相同的子问题，而不是总是产生新的子问题（算法简介 by CLRS）
这两个定义（以及互联网上的许多其他定义）似乎都归结为一个具有重叠子问题的问题，如果找到它的解决方案涉及多次解决相同的子问题。换句话说，有许多小的子问题，在寻找原始问题的解决方案的过程中被多次计算。一个经典的例子是斐波那契算法，很多例子都用它来让人们理解这一点属性。
直到几天前，生活还很美好，直到我发现 Kadane 的算法让我质疑重叠子问题的定义。这主要是因为人们对它是否是DP算法有不同的看法：
- Kadane 算法中的动态规划方面
- Is Kadane's algorithm consider DP or not? And how to implement it recursively?
- Dynamic Programming vs Memoization (see my comment)
为什么有人不会将 Kadane 的算法视为 DP 算法的最令人信服的原因是每个子问题只会 在递归实现中 出现并计算一次 [3] ，因此它不包含重叠的子问题 属性。然而，互联网上的许多文章认为 Kadane 的算法是 DP 算法，这让我质疑我对 重叠子问题 的理解首先意味着什么。
人们似乎对 重叠子问题 属性 的解释不同。对于简单的问题（例如 Fibonacci 算法）很容易看到它，但是一旦您引入 Kadane 的算法，事情就会变得非常不清楚。如果有人能提供进一步的解释，我将不胜感激。
您已经阅读了很多相关内容。我唯一要补充的是：
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])
如您所见，max_subarray_to() 对每个 i 计算两次。 Kadane 的算法记住了这些，将其从 O(n2) 变为 O(n)
...但是正如@Stef所说，你怎么称呼它并不重要，只要你理解它。
要使动态规划适用，问题必须具备两个关键属性：最优子结构和重叠子问题[1]。对于这个问题，我们只关注后者属性。
重叠子问题有多种定义，其中两个是：
- 如果问题可以分解为可多次重复使用的子问题，则称该问题具有重叠子问题或问题的递归算法解决同一个子问题一遍又一遍，而不是总是产生新的子问题 [2].
- 要应用动态规划，优化问题必须具备的第二个要素是 space 子问题必须“小”，因为该问题的递归算法可以求解一遍又一遍地解决相同的子问题，而不是总是产生新的子问题（算法简介 by CLRS）
这两个定义（以及互联网上的许多其他定义）似乎都归结为一个具有重叠子问题的问题，如果找到它的解决方案涉及多次解决相同的子问题。换句话说，有许多小的子问题，在寻找原始问题的解决方案的过程中被多次计算。一个经典的例子是斐波那契算法，很多例子都用它来让人们理解这一点属性。
直到几天前，生活还很美好，直到我发现 Kadane 的算法让我质疑重叠子问题的定义。这主要是因为人们对它是否是DP算法有不同的看法：
- Kadane 算法中的动态规划方面
- Is Kadane's algorithm consider DP or not? And how to implement it recursively?
- Dynamic Programming vs Memoization (see my comment)
为什么有人不会将 Kadane 的算法视为 DP 算法的最令人信服的原因是每个子问题只会 在递归实现中 出现并计算一次 [3] ，因此它不包含重叠的子问题 属性。然而，互联网上的许多文章认为 Kadane 的算法是 DP 算法，这让我质疑我对 重叠子问题 的理解首先意味着什么。
人们似乎对 重叠子问题 属性 的解释不同。对于简单的问题（例如 Fibonacci 算法）很容易看到它，但是一旦您引入 Kadane 的算法，事情就会变得非常不清楚。如果有人能提供进一步的解释，我将不胜感激。
您已经阅读了很多相关内容。我唯一要补充的是：
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])
如您所见，max_subarray_to() 对每个 i 计算两次。 Kadane 的算法记住了这些，将其从 O(n2) 变为 O(n)
...但是正如@Stef所说，你怎么称呼它并不重要，只要你理解它。