algorithm - Kadane 算法中的动态规划方面

Question

Initialize:
    max_so_far = 0
    max_ending_here = 0

Loop for each element of the array
   (a) max_ending_here = max_ending_here + a[i]
   (b) if(max_ending_here < 0)
         max_ending_here = 0
   (c) if(max_so_far < max_ending_here)
          max_so_far = max_ending_here
 return max_so_far

谁能帮助我理解上述算法中的最优子结构和重叠问题(DP 的面包和黄油)？

Answer 1

根据 this 重叠子问题 的定义，Kadane 算法的递归公式 (f[i] = max(f[i - 1] + a[i], a[i]) ) 不展示此属性。在朴素的递归实现中，每个子问题只会计算一次。

然而，根据其定义，它确实表现出最佳子结构 here :我们使用较小子问题的解决方案来找到给定问题的解决方案(f[i] 使用 f[i - 1])。

考虑动态规划定义 here :

In mathematics, computer science, and economics, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems1 and optimal substructure (described below). When applicable, the method takes far less time than naive methods that don't take advantage of the subproblem overlap (like depth-first search).

The idea behind dynamic programming is quite simple. In general, to solve a given problem, we need to solve different parts of the problem (subproblems), then combine the solutions of the subproblems to reach an overall solution. Often when using a more naive method, many of the subproblems are generated and solved many times. The dynamic programming approach seeks to solve each subproblem only once, thus reducing the number of computations

这为 Kadane 的算法是否可以被视为 DP 算法留下了解释空间:它确实通过将问题分解为更简单的子问题来解决问题，但其核心递归方法不会生成重叠的子问题，这正是 DP旨在有效地处理 - 所以这将超出 DP 的专业范围。

另一方面，您可以说基本递归方法没有必要导致重叠的子问题，但这会使任何递归算法成为 DP 算法，在我看来这会使 DP 的范围太广.然而，我不知道文献中有什么可以明确解决这个问题的，所以我不会给学生打分，也不会不考虑他们给它贴上标签的书或文章。

所以我会说它不是 DP 算法，只是一种贪婪和/或递归算法，具体取决于实现。出于上述原因，我会从算法的角度将其标记为贪心，但客观上我会认为其他解释同样有效。