Is prefix sum included in dynamic programming?

Question

I've been solving algorithm problems, and I'm a bit confused about the terms.

When we want to calculate prefix sum (or cumulative sum) like the code below, can we say that we are using dynamic programming?

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]

According to the definition in this page,

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

In my prefix_sum algorithm, the current calculation (prefix_sum[i]) is divided into similar sub-problems (prefix_sum[i - 1] + nums[i - 1]) so that the previous result (prefix_sum[i - 1]) can be re-used. So I am assuming that calculating prefix sum is one of the applications of dynamic programming.

Can I say it's dynamic programming, or should I use different terms? (Especially, I am thinking about the situation in coding interviews.)

Answer 1

No, the correct term is memoization, not dynamic programming. Dynamic programming requires the problem to have optimal substructure as well as overlapping subproblems. Prefix sum has optimal substructure but it does not have overlapping subproblems. Therefore, this optimization should be called memoization.

Answer 2

Yes, prefix sums can be considered as a form of Dynamic Programming. It is the simplest way to calculate the sum of a range given a static array by using a prefix array which stores data based on previous sums.

Prefix Sum Array Construction Runtime = O(n)
Prefix Sum Query Runtime = O(1)