Formatted question description: https://leetcode.ca/all/1959.html

# 1959. Minimum Total Space Wasted With K Resizing Operations

## Level

Medium

## Description

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`

, `size_t`

, 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 time `t`

is defined as `size_t - nums[t]`

, and the **total** space wasted is the **sum** of the space wasted across every time `t`

where `0 <= t < 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.

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

**Constraints:**

`1 <= nums.length <= 200`

`1 <= nums[i] <= 10^6`

`0 <= k <= nums.length - 1`

## Solution

Use dynamic programming. Create a 2D array `dp`

with `k + 1`

rows and `nums.length`

columns, where `dp[i][j]`

represents the minimum space wasted with at most `j`

resizings. For each `dp[i][j]`

, the initial value is infinity. Loop over `l`

from `j`

to `i`

backwards. For each `l`

, calculate the `sum`

of `nums[i..j]`

and the `maxSize`

of `nums[i..j]`

. If `i > 0 || l == 0`

, calculate `dp[i][j]`

as the minimum of `dp[i - 1][l - 1] + (maxSize * (j - l + 1) - sum)`

, where `dp[i - 1][l - 1] = 0`

for `l == 0`

. Finally, return `dp[k][nums.length - 1]`

.

```
class Solution {
public int minSpaceWastedKResizing(int[] nums, int k) {
int length = nums.length;
int[][] dp = new int[k + 1][length];
for (int i = 0; i <= k; i++) {
for (int j = 0; j < length; j++) {
dp[i][j] = Integer.MAX_VALUE;
int sum = 0, maxSize = 0;
for (int l = j; l >= i; l--) {
sum += nums[l];
maxSize = Math.max(maxSize, nums[l]);
if (i > 0 || l == 0)
dp[i][j] = Math.min(dp[i][j], (l > 0 ? dp[i - 1][l - 1] : 0) + (maxSize * (j - l + 1) - sum));
}
}
}
return dp[k][length - 1];
}
}
```