1959. Minimum Total Space Wasted With K Resizing Operations

class Solution:
    def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:
        """tc O(N*N*K)
        """
        @lru_cache(None)
        def dfs(k, cur):
            if cur == len(A):
                return 0
            if k < 0 :
                return float('inf')
            maxv = 0
            sum_by_i = 0
            res = float('inf')
            for j in range(cur,len(A)):
                maxv = max(maxv, A[j])
                sum_by_i += A[j]
                diff = maxv * (j-cur+1) - sum_by_i
                res = min(res, diff + dfs(k-1,j+1))
            return res 
        return dfs(k,0)

class Solution:
    def minSpaceWastedKResizing(self, A: List[int], k: int) -> int:
        """tc O(N*N*K)
        """
        psum = [0] 
        for i in range(len(A)):
            psum.append(psum[-1] + A[i])
        
        @lru_cache(None)
        def dfs(k,start,end):
            if k == 0:
                return max(A[start:end+1]) * (end-start+1) - (psum[end+1]-psum[start])

            res = float('inf')
            for cut_end in range(start,end+1-k):
                res = min(res, dfs(0, start, cut_end) + dfs(k-1, cut_end+1, end))
            return res
        
        return dfs(k,0,len(A)-1)