[数据结构与算法]LeetCode 5828. K 次调整数组大小浪费的最小总空间（动态规划）

题目：

5828. K 次调整数组大小浪费的最小总空间

nums[i]?是?i?时刻数组中的元素数目

k?表示可以?调整?数组大小的?最多?次数

t?时刻数组的大小?size[t]?必须大于等于?nums[t]

浪费的总空间 = Σ（size[t]?-?nums[t])

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-total-space-wasted-with-k-resizing-operations
?

题解：

动态规划，以 f(i,j) 表示 数组截止到 i ∈[0,n)，调整 j ∈[0,k] 次，“浪费的最小总空间”

则有:?

其中，g(s,t) 表示从 nums[s] 到 nums[t]，无调整，“浪费的最小总空间”

源码：

class Solution:
    def minSpaceWastedKResizing(self, nums: list[int], k: int) -> int:
        n = len(nums)
        g = [[0] * n for _ in range(n)]
        for s in range(n):
            maxnum = nums[s]
            sumary = nums[s]
            for t in range(s + 1, n):
                sumary += nums[t]
                maxnum = max(maxnum, nums[t])
                g[s][t] = maxnum * (t - s + 1) - sumary
        
        f = g[0].copy()
        for _ in range(k):
            for i in reversed(range(n)):
                f[i] = min((f[p] + g[p + 1][i] for p in range(i)), default=float('inf'))

        return f[-1]