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];
}
}