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

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

Return the minimum total space wasted if you can resize the array at most k times.

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

&nbsp;
Example 1:

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


Example 2:

Input: nums = [10,20,30], k = 1
Output: 10
Explanation: 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.


Example 3:

Input: nums = [10,20,15,30,20], k = 2
Output: 15
Explanation: 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.


&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 200
	1 &lt;= nums[i] &lt;= 106
	0 &lt;= k &lt;= nums.length - 1


class Solution:
    def minSpaceWastedKResizing(self, A: List[int], K: int) -> int:
        def waste(i, j, h):
            sumI = sums[i-1] if i > 0 else 0
            return (j-i+1)*h - sums[j] + sumI
        
        def dp(i, k):
            if i <= k:
                return 0
            if k < 0:
                return MAX
            if (i, k) in memoize:
                return memoize[(i, k)]
            
            _max = A[i]
            r = MAX
            for j in range(i-1, -2, -1):
                r = min(r, dp(j, k-1) + waste(j+1, i,  _max))
                _max = max(_max, A[j])

            memoize[(i, k)] = r
            return r
        
        sums = list(accumulate(A))
        n = len(A)
        MAX = 10**6*200
        memoize = {}

        return dp(n-1, K)
class Solution {

// dp[idx][k]=minimum wasted space in between [idx....n-1] if we resize the region k times 

    int INF=200 *(int)1e6; // according to constarints { 1 <= nums.length <= 200 , 1 <= nums[i] <= 106 }
    public int minSpaceWastedKResizing(int[] nums, int k) {
        
        int dp[][]=new int[nums.length+1][k+1];
        memeset(dp, -1);
        return f(dp, 0, k, nums);
        
    }
    
    int f(int dp[][], int idx, int k, int nums[])
    {
        if(idx==nums.length)
            return 0;
        if(k==-1)
            return INF;
        
        if(dp[idx][k] != -1)
            return dp[idx][k];
        
        int ans=INF, max=nums[idx], sum=0;
        
        for(int j=idx; j<nums.length; ++j)
        {
            max=Math.max(max, nums[j]);
            sum+=nums[j];
        /**    
             total waste in between [idx...j] would be
             summation of (max-nums[idx] + max-nums[idx+1]....max-nums[j])
             length would be (j-idx+1) and these summation would be
             (j-idx+1) * max upto j - (nums[idx]+nums[idx+1]....+nums[j]
 
            as i have made one partition in between [idx...j] then remainig (k-1) partitions would be in between [j+1....n-1]
            and that value will be calculated by the recursion and we have to take the minimum answer from all these combinations 
            and to avoid tle we are using memozization
        **/
            int total_waste_upto_j=(j-idx+1)*max - sum;
            ans=Math.min(ans,  total_waste_upto_j + f(dp, j+1, k-1, nums));
            
        }
        
        return dp[idx][k]=ans;
    }
    
    void memeset(int dp[][], int val)
    {
        for(int x[]: dp)
            Arrays.fill(x, val);
    }
}

// tc: O(n^2 * k) there will be total (n*k) states  because for each k there are n possibilities and for each n there will be loop running n times
// so in total there will be O(n^2 * k) [because k<n]
// sc: O(n*k)
class Solution {
public:
    int dp[205][205];
    #define maxi pow(10,8)
    #define ll long long
    int dfs(vector<int>& nums, int idx, int k)
    {
        int n = nums.size();
        if(idx==n) return 0;
        if(k<0) return maxi;
        if(dp[idx][k]!=-1) return dp[idx][k];
        ll sum = 0, mx = 0, ans = maxi;
        for(int i=idx; i<n; i++)
        {
            sum += nums[i];
            mx = max(mx,(ll)nums[i]);
            ans = min(ans,mx*(i-idx+1)-sum + dfs(nums,i+1,k-1));
        }
        return dp[idx][k] = ans;
    }

    int minSpaceWastedKResizing(vector<int>& nums, int k) {
        memset(dp,-1,sizeof(dp));
        return dfs(nums,0,k);
    }
};
var minSpaceWastedKResizing = function(nums, k) {
    var prefixSum = []; // prefix is index 1 based
    var rangeMax = []; // index 0 based
    var sum = 0;
    prefixSum[0] = 0; 
    for (var i = 0; i < nums.length; i++) {
        sum += nums[i];
        prefixSum[i + 1] = sum;
    }
    for (var i = 0; i < nums.length; i++) {
        var max = -Infinity;
        rangeMax[i] = [];
        for (var j = i; j < nums.length; j++) {
            max = Math.max(nums[j], max);
            rangeMax[i][j] = max;
        }
    }
    var f = []; // f[i][j] is resize i times to get minimun with index j - 1 to get minimum space.
    f[0] = [];
    for (var i = 0; i <= k; i++) {
        f[i] = [];
        f[i][0] = 0;
    }
    for (var j = 1; j <= nums.length; j++) {
        f[0][j] = rangeMax[0][j - 1] * j - prefixSum[j];
    }

    for (var i = 1; i <= k; i++) {
        for (var j = 1; j <= nums.length; j++) {
            f[i][j] = Infinity;
            for (var m = 1; m <= j; m++) {
                f[i][j] = Math.min(f[i][j], f[i - 1][m - 1] + rangeMax[m - 1][j - 1] * (j - m + 1) - (prefixSum[j] - prefixSum[m - 1]));
            }
        }
    }
    return f[k][nums.length];
};
Minimum Total Space Wasted With K Resizing Operations