list - 动态规划中包含前缀和吗？

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]

根据这个page中的定义,

Dynamic programming is used where we have problems, which can bedivided into similar sub-problems so that their results can bere-used.

在我的prefix_sum算法中，当前的计算(prefix_sum[i])被分成类似的子问题(prefix_sum[i - 1] + nums[i - 1])，使得之前的结果(prefix_sum[i - 1] ])可以重复使用。所以我假设计算前缀和是动态规划的应用之一。

我可以说这是动态规划，还是应该使用不同的术语？ (特别是我正在思考编码面试中的情况。)

Answer 1

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