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 solution optimizes the problem down to an O(1)
operation, once the cache has been populated:
1from itertools import accumulate
2
3nums = [*range(1, 10)]
4acc = [*accumulate(nums)]
5
6asum = lambda i, j: acc[j] - (0, acc[i - 1])[i > 0]
7
8print(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
.
See also: