<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>

class Solution:
    def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:
        # nums[i] is num elts at time i
        # can resize k times, k+1 sizes total
        # size[i] >= nums[i] req. obv.
        

        # suppose we can't resize: pick max

        # if we can resize once: pick an index i at which we resize
        #   choose max(left) and max(right)
        
        # suppose we know wasted space on i+1: with r-1 resizes
        #     if we don't resize at i then wasted space... tough to combine,
        # not stateless because of cumulative max so not suitable for DP

        # can we do a brute-force top-down DFS solution?
        #    at each index we can resize or not
        # that gets tricky too because if we don't resize we need the max of later elements

        # divide and conquer is too greedy for what we need

        # well... we have to start somewhere, and we have k+1 sizes we can pick

        # if k == 0 then we return N*max - sum
        # if k+1 >= N we return 0

        # wlog we have to put at least one element in the first of the k+1 partitions
        #   > one element: waste max(0)-sum(0) space plus wasted space on 1: with k-1 resizes
        #   > two elements: waste max(0..1)-sum(0..1) space plus wasted space on 2: with k-1
        #   ... and so on

        N = len(nums)
        
        if k == 0: return max(nums)*len(nums) - sum(nums)
        if k+1 >= N: return 0

        cmax_right = nums[:]
        for i in range(N-2, -1, -1): cmax_right[i] = max(cmax_right[i], cmax_right[i+1])

        csum_right = nums[:]
        for i in range(N-2, -1, -1): csum_right[i] += csum_right[i+1]

        @cache
        def minWasted(i: int, r: int) -> int:
            """Returns min wasted space where we group elements i: into r remaining partitions"""
            if N-i <= r: return 0 # unique size for each element possible

            if r == 1:
                return cmax_right[i]*(N-i) - csum_right[i] # max*N - sum over i..N-1

            cmax = 0
            csum = 0
            best = math.inf
            for j in range(i, N-r+1): # upper bound: when N-(j+1) == r-1, minWasted is zero
                cmax = max(cmax, nums[j])
                csum += nums[j]
                best = min(best, cmax*(j-i+1)-csum+minWasted(j+1, r-1)) # N-r == j

            return best

        return minWasted(0, k+1)
1766