前缀和包含在动态编程中吗

Question

我一直在解决算法问题，对这些术语有点困惑。

当我们想像下面的代码一样计算前缀和(或累积和(时，我们可以说我们在使用动态编程吗？

def calc_prefix_sum(nums):
N = len(nums)
prefix_sum = [0] * (N + 1)
for i in range(1, N + 1):
prefix_sum[i] = prefix_sum[i - 1] + nums[i - 1]
return prefix_sum
nums = [1, 3, 0, -2, 1]
print(calc_prefix_sum(nums))

[0, 1, 4, 4, 2, 3]

根据本页的定义，

当我们遇到问题时，可以使用动态编程划分为类似的子问题，以便它们的结果可以重复使用。

在我的prefix_sum算法中，当前的计算(prefix_sum[i](被划分为类似的子问题(prefix-sum[i-1]+nums[i-1](，以便可以重用以前的结果(prefix_sum[i-1]。所以我假设计算前缀和是动态编程的应用之一。

我可以说这是动态编程吗？还是应该使用不同的术语？(尤其是，我在思考编码面试中的情况。(

Answer 1

不，正确的术语是内存化，而不是动态编程。动态规划要求问题具有最优子结构以及重叠子问题。前缀和具有最优子结构，但不具有重叠子问题。因此，这种优化应该被称为记忆化。

Answer 2

是的，前缀和可以被视为动态编程的一种形式。这是通过使用前缀数组来计算给定静态数组的范围的和的最简单方法，该数组存储基于先前和的数据。

前缀和数组构造运行时=O(n(
前缀和查询运行时=0(1(

Answer 3

人们常说Kadane的算法是DP，而Kadane算法距离前缀和只有1if语句。

def maxSubArray(nums: List[int]) -> int:
for i in range(1, len(nums)):
if nums[i-1] > 0:
nums[i] = nums[i-1] + nums[i]
return max(nums)

如果你试图递归地计算前缀和，你最终会得到一个没有记忆的O(n^2(，而是一个有记忆的O算法。这是因为重叠的子问题。

nums = [1, 3, 0, -2, 1]
def cumsum(i):
if i < 0:
return 0
return nums[i] + cumsum(i-1)
prefix_sum = [cumsum(i) for i in range(len(nums))]

我们可以看到cumsum(0)被调用了5次，因为递归在返回之前必须达到基本情况，并且我们调用函数5次。cumsum(1)被调用4次，cumsum(2)被调用3次，依此类推

这就是为什么我会说前缀和既有最优子问题，也有重叠子问题。