动态编程（DP）中有哪些重叠的子问题？ [英] What are overlapping subproblems in Dynamic Programming (DP)?

问题描述

要使动态编程适用，必须具有两个关键属性：最优子结构和重叠子问题 [1] 。对于这个问题，我们将仅关注后者的属性。

There are two key attributes that a problem must have in order for dynamic programming to be applicable: optimal substructure and overlapping subproblems [1]. For this question, we going to focus on the latter property only.

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

There are various definitions for overlapping subproblems, two of which are:

• 如果一个问题可以分解为多个子问题，这些问题可以重复使用几次，则该问题可以重复使用 OR 该问题可以一遍又一遍地解决相同的子问题，而不是总是生成新的子问题 [2]
  
• 要应用动态编程的优化问题所必须具有的第二个要素是子问题的空间必须小。从某种意义上说，一个递归算法可以反复解决相同的子问题，而不是总产生新的子问题（CLRS的算法简介）

• A problem is said to have overlapping subproblems if the problem can be broken down into subproblems which are reused several times OR a recursive algorithm for the problem solves the same subproblem over and over rather than always generating new subproblems [2].
• A second ingredient that an optimization problem must have for dynamic programming to apply is that the space of subproblems must be "small" in the sense that a recursive algorithm for the problem solves the same subproblems over and over, rather than always generating new subproblems (Introduction to Algorithms by CLRS)

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

Both definitions (and lots of others on the internet) seem to boil down to a problem having overlapping subproblems if finding its solution involves solving the same subproblems multiple times. In other words, there are many small sub-problems which are computed many times during finding the solution to the original problem. A classic example is the Fibonacci algorithm that lots of examples use to make people understand this property.

直到几天前，生活一直很美好，直到我发现 Kadane的算法使我质疑重叠的子问题定义。这主要是由于人们对于它是否是DP算法存在不同的看法：

Until a couple of days ago, life was great until I discovered Kadane's algorithm which made me question the overlapping subproblems definition. This was mostly due to the fact that people have different views on whether or NOT it is a DP algorithm:

• Kadane算法
  


• Kadane的算法是否考虑DP？以及如何递归实现它？


• 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] 中只会出现并被计算一次，因此它不会t包含重叠的子问题属性。但是，互联网上的许多文章都将Kadane的算法视为DP算法，这使我质疑重叠子问题的含义。

The most compelling reason why someone wouldn't consider Kadane's algorithm a DP algorithm is that each subproblem would only appear and be computed once in a recursive implementation [3], hence it doesn't entail the overlapping subproblems property. However, lots of articles on the internet consider Kadane's algorithm to be a DP algorithm, which made me question my understanding of what overlapping subproblems means in the first place.

人们似乎对重叠子问题属性的解释有所不同。斐波那契（Fibonacci）算法等简单问题很容易看出来，但是一旦您引入Kadane算法，事情就变得非常不清楚。如果有人可以提供进一步的解释，我将不胜感激。

People seem to interpret the overlapping subproblems property differently. It's easy to see it with simple problems such as the Fibonacci algorithm but things become very unclear once you introduce Kadane's algorithm for instance. I would really appreciate it if someone could offer some further explanation.

推荐答案

您已经了解了很多。我唯一要添加的是：

You've read so much about this already. The only thing I have to add is this:

Kadane算法中重叠的子问题在这里：

The overlapping subproblems in Kadane's algorithm are here:

max_subarray = max（从i = 1到n [ max_subarray_to（i）]）

max_subarray = max( from i=1 to n [ max_subarray_to(i) ] )

max_subarray_to（i）= max（ max_subarray_to（i-1） + array [i ]，array [i]）

max_subarray_to(i) = max(max_subarray_to(i-1) + array[i], array[i])

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

As you can see, max_subarray_to() is evaluated twice for each i. Kadane's algorithm memoizes these, turning it from O(n²) to O(n)

...但是正如@Stef所说，没关系只要您了解它就可以叫它。

... But as @Stef says, it doesn't matter what you call it, as long as you understand it.

这篇关于动态编程（DP）中有哪些重叠的子问题？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！