dp array sum

← 🏠

You might be asked to return the sum of an array between i and j, repeatedly. Computing sums is an O(n) operation so a caching a solution optimizes the problem down to an O(1) operation, once the cache has been populated:

1 from itertools import accumulate
2 
3 nums = [*range(1, 10)]
4 acc = [*accumulate(nums)]
5 
6 asum = lambda i, j: acc[j] - (0, acc[i - 1])[i > 0]
7 
8 print(asum(1, 3))

The trick boils down to running an accumulate, and substracting the accumulated value at i-1 from the accumulated value at j.