Minimum Total Space Wasted With K Resizing Operations LeetCode solution in Python

1
class Solution:
2
    def minSpaceWastedKResizing(self, A: List[int], K: int) -> int:
3
        def waste(i, j, h):
4
            sumI = sums[i - 1] if i > 0 else 0
5
            return (j - i + 1) * h - sums[j] + sumI
6

7
        def dp(i, k):
8
            if i <= k:
9
                return 0
10
            if k < 0:
11
                return MAX
12
            if (i, k) in memoize:
13
                return memoize[(i, k)]
14

15
            _max = A[i]
16
            r = MAX
17
            for j in range(i - 1, -2, -1):
18
                r = min(r, dp(j, k - 1) + waste(j + 1, i, _max))
19
                _max = max(_max, A[j])
20

21
            memoize[(i, k)] = r
22
            return r
23

24
        sums = list(accumulate(A))
25
        n = len(A)
26
        MAX = 10**6 * 200
27
        memoize = {}
28

29
        return dp(n - 1, K)