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

根据重叠子问题的这个定义,Kadane算法()的递归公式没有表现出这种性质.每个子问题只能在一个简单的递归实现中计算一次.f[i] = max(f[i - 1] + a[i], a[i])

但它确实表现出最优子根据其定义在这里:我们使用的解决方案,以更小的子问题,以便找到解决我们给定的问题(f[i]用途f[i - 1]).

在这里考虑动态编程定义:

在数学,计算机科学和经济学中,动态规划是一种通过将复杂问题分解为更简单的子问题来解决复杂问题的方法.它适用于表现出重叠子问题1和最佳子结构(下面描述)的特性的问题.适用时,该方法比不利用子问题重叠(如深度优先搜索)的朴素方法花费的时间少得多.

动态编程背后的想法非常简单.一般来说,为了解决给定的问题,我们需要解决问题的不同部分(子问题),然后结合子问题的解决方案来达到整体解决方案.通常在使用更天真的方法时,会产生并解决许多子问题.动态编程方法只寻求解决每个子问题一次,从而减少计算次数

这为解释Kadane的算法是否可以被认为是DP算法留下了空间:它确实通过将其分解为更容易的子问题来解决问题,但其核心递归方法不会产生重叠的子问题,这就是DP的意思有效处理 - 所以这将使它超出DP的专长.

另一方面,你可以说基本的递归方法没有必要导致重叠的子问题,但是这会使任何递归算法成为DP算法,这在我看来会给DP一个太宽泛的范围.我不知道文献中的任何内容肯定会解决这个问题,所以我不会记下一个学生,也不会在他们标记它的方式上考虑一本书或文章.

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