<p>You are currently designing a dynamic array. You are given a <strong>0-indexed</strong> integer array <code>nums</code>, where <code>nums[i]</code> is the number of elements that will be in the array at time <code>i</code>. In addition, you are given an integer <code>k</code>, the <strong>maximum</strong> number of times you can <strong>resize</strong> the array (to<strong> any</strong> size).</p>

<p>The size of the array at time <code>t</code>, <code>size<sub>t</sub></code>, must be at least <code>nums[t]</code> because there needs to be enough space in the array to hold all the elements. The <strong>space wasted</strong> at&nbsp;time <code>t</code> is defined as <code>size<sub>t</sub> - nums[t]</code>, and the <strong>total</strong> space wasted is the <strong>sum</strong> of the space wasted across every time <code>t</code> where <code>0 &lt;= t &lt; nums.length</code>.</p>

<p>Return <em>the <strong>minimum</strong> <strong>total space wasted</strong> if you can resize the array at most</em> <code>k</code> <em>times</em>.</p>

<p><strong>Note:</strong> The array can have <strong>any size</strong> at the start and does<strong> not </strong>count towards the number of resizing operations.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [10,20], k = 0
<strong>Output:</strong> 10
<strong>Explanation:</strong> size = [20,20].
We can set the initial size to be 20.
The total wasted space is (20 - 10) + (20 - 20) = 10.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [10,20,30], k = 1
<strong>Output:</strong> 10
<strong>Explanation:</strong> size = [20,20,30].
We can set the initial size to be 20 and resize to 30 at time 2. 
The total wasted space is (20 - 10) + (20 - 20) + (30 - 30) = 10.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [10,20,15,30,20], k = 2
<strong>Output:</strong> 15
<strong>Explanation:</strong> size = [10,20,20,30,30].
We can set the initial size to 10, resize to 20 at time 1, and resize to 30 at time 3.
The total wasted space is (10 - 10) + (20 - 20) + (20 - 15) + (30 - 30) + (30 - 20) = 15.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 200</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>6</sup></code></li>
	<li><code>0 &lt;= k &lt;= nums.length - 1</code></li>
</ul>

# from functools import lru_cache
# class Solution:
#     def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:
#         @lru_cache(None)
#         def dp(i, key, k, max_key):
#             if i == len(nums):
#                 return 0
            
            
#             not_swap = float('inf')
#             if nums[i] <= key: 
#                 not_swap  = key - nums[i] + dp(i+1, key, k, max_key)
            
#             swap = float('inf')
#             if k > 1 and nums[i] > key:
#                 key = nums[i]
#                 swap =  key - nums[i] + dp(i+1, key, k-1, max_key)
#             elif k == 1:
#                 key = max_key
#                 swap = key - nums[i] + dp(i+1, key, k-1, max_key)
            
#             must_swap = float('inf')
#             if k >= 1:
#                 key = nums[i]
#                 must_swap = key - nums[i] + dp(i+1, key , k-1, max_key)

#             return min(swap,not_swap,must_swap)
        
#         minimum_value = float('inf')
#         max_key = max(nums)
        
#         for i in range(len(nums)):
#             minimum_value = min(minimum_value, dp(0, nums[i], k, max_key))
        
#         return minimum_value


from typing import List
from functools import lru_cache

class Solution:
    def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:
        n = len(nums)
        
        # Precompute the maximum in every subarray nums[i:j+1]
        max_in_subarray = [[0] * n for _ in range(n)]
        for i in range(n):
            current_max = nums[i]
            for j in range(i, n):
                current_max = max(current_max, nums[j])
                max_in_subarray[i][j] = current_max
        
        # Precompute the waste in every subarray nums[i:j+1]
        waste_in_subarray = [[0] * n for _ in range(n)]
        for i in range(n):
            for j in range(i, n):
                max_val = max_in_subarray[i][j]
                waste_in_subarray[i][j] = sum(max_val - nums[t] for t in range(i, j + 1))
        
        # DP to calculate the minimum space wasted
        @lru_cache(None)
        def dp(start: int, k: int) -> int:
            if start == n:
                return 0
            if k < 0:
                return float('inf')
            
            min_waste = float('inf')
            for end in range(start, n):
                current_waste = waste_in_subarray[start][end]
                remaining_waste = dp(end + 1, k - 1)
                min_waste = min(min_waste, current_waste + remaining_waste)
            
            return min_waste
        
        return dp(0, k)

2941