<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:
    # My first attempt did not work
    # In my second attempt I will frame this as the total space saved by 
    # resizing the array and starting with the maximum of nums[i..n-1]
    # where i is resizing point
    def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:
        # space_saved[i][j] is the total space saved when you allow k
        # resize operations when you start 
        cumulative_sum = [0]* len(nums)
        cumulative_sum[0] = nums[0] # sum of all numbers from 0-1
        for i in range(1,len(nums)):
            cumulative_sum[i] = cumulative_sum[i-1] + nums[i]
        # make an array max_v[i][k] which records the maximum of subarray
        # nums[i...i+k] exclusive of size k+1.
        # print(cumulative_sum)
        max_v = []
        for i in range(len(nums)):
            max_v.append([nums[i]])
            for j in range(i+1, len(nums)):
                max_v[i].append(max(max_v[i][-1], nums[j]))
        # print(max_v)
        # Total space wasted between i to j if you don't resize between i and j is
        #Space_NRS(i,j) = max_v[i][j-i] * (size of subarray i.e. j-i+1) - (cumulative_sum[j] - cumulative_sum[i-1]) 

        # Minimum space wasted between i to n - 1 with at most k resizes
        # WS(i, k) = MIN(WS(i, k-1) ,MIN(Space_NRS(i,j-1) + WS(j, k-1))) for i < j <= n-1

        dp_table = []
        # dp_table[m][i] represents the WS(i, m-1)
        for m in range(k+1):
            for i in range(len(nums)):
                dp_table.append([])
                if m == 0:
                    # For no resize (k=0) WS(i,0) is Space_NRS[i,n-1]
                    cum_i_minus_1 = cumulative_sum[i-1] if i > 0 else 0
                    dp_table[m].append(max_v[i][-1] * (len(nums) - i)  - (cumulative_sum[-1] - cum_i_minus_1))
                else:
                    max_s = dp_table[m-1][i]
                    for j in range(i+1, len(nums)):
                        cum_i_minus_1 = cumulative_sum[i-1] if i > 0 else 0
                        space_nrs = max_v[i][j-1-i] * (j-i) - (cumulative_sum[j-1] - cum_i_minus_1)
                        # print(f" space_nrs({i},{j-1}) = {space_nrs}")
                        if space_nrs + dp_table[m-1][j] < max_s:
                            max_s = space_nrs + dp_table[m-1][j]
                    dp_table[m].append(max_s)
        # print(dp_table)
        return dp_table[m][0]
2261