'Is prefix sum included in dynamic programming?

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.)

listdynamic-programmingcumulative-sumprefix-sum


Solution 1:[1]

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)

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 BooleanCube

Related Questions