You are given an array nums of n positive integers, where nums[i] represents the size of the i-th element to be inserted into a dynamic array. The dynamic array starts empty and is resized to fit elements as they are added.
Each time you insert an element, if the current array's capacity is less than the required size, you must resize it. Resizing means increasing the capacity to a new size, at least as large as the largest element so far.
You are allowed to perform at most k resizing operations. After each resizing, you can pick the new capacity as any integer at least as large as the largest element in the current segment.
The wasted space for a segment is defined as the total capacity allocated for that segment minus the sum of the elements in that segment. Your goal is to partition the array into at most k+1 contiguous segments (each corresponding to a resize), and for each segment, pick a capacity (at least as large as the largest element in the segment) to minimize the total wasted space.
Return the minimum total wasted space possible after at most k resizes.
nums.length ≤ 200nums[i] ≤ 106k ≤ nums.length - 1
At first glance, the problem looks like a variant of dynamic array resizing, but with the twist that you are allowed a limited number of resizes (k), and you want to minimize the wasted space. Brute-force would mean trying all possible ways to partition the array into up to k+1 segments, and for each, computing the optimal capacity. However, with up to 200 elements, this quickly becomes intractable.
Recognizing the structure, this is a classic "partition the array into segments with minimal cost" problem, where cost for each segment is determined by the largest element (capacity) and the sum of its elements. Dynamic programming is a natural fit, as the problem has optimal substructure: the best solution for the first i elements and k resizes can be built from solutions to smaller prefixes and fewer resizes.
We need to efficiently compute, for any segment, the maximum and sum. Precomputing prefix sums and using a sliding window for maximums can help with this.
dp[i][k] be the minimum wasted space for the subarray nums[0..i] with at most k resizes.
dp[-1][*] = 0 (no elements, no waste).
i (ending index of current segment), and each possible previous partition point j (-1 <= j < i), consider making a new resize at j+1:
maxNum and sumNum for nums[j+1..i].
(i-j) * maxNum - sumNum.
dp[i][k] as min(dp[i][k], dp[j][k-1] + wasted).
dp[n-1][k] is the answer.
This approach ensures that for each possible number of resizes and each subarray, we always consider the optimal way to partition and allocate capacity.
Example Input: nums = [10, 20, 15, 30, 20], k = 2
k=2 resizes).
[10, 20], [15, 30], [20].
dp[i][k]), and for each, we loop over O(n) previous split points. So total time is O(n2k).
The problem is a classic DP partitioning challenge, where each segment's cost depends on its largest element and sum. By defining a DP state representing the minimum wasted space up to each index with a given number of resizes, and efficiently computing segment costs, we can solve the problem in O(n2k) time. Key insights are the use of prefix sums, careful state transitions, and recognizing the optimal substructure. This approach is robust and elegant, leveraging classic dynamic programming principles.
from typing import List
class Solution:
def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:
n = len(nums)
prefix_sum = [0] * (n + 1)
for i in range(n):
prefix_sum[i+1] = prefix_sum[i] + nums[i]
# dp[i][j]: min wasted space for first i elements with j resizes
dp = [[float('inf')] * (k+2) for _ in range(n+1)]
dp[0][0] = 0
for i in range(1, n+1):
for resizes in range(1, k+2):
max_num = 0
# Try all possible partitions
for j in range(i-1, -1, -1):
max_num = max(max_num, nums[j])
segment_sum = prefix_sum[i] - prefix_sum[j]
wasted = max_num * (i - j) - segment_sum
dp[i][resizes] = min(dp[i][resizes], dp[j][resizes-1] + wasted)
return min(dp[n][1:k+2])
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
class Solution {
public:
int minSpaceWastedKResizing(vector<int>& nums, int k) {
int n = nums.size();
vector<int> prefix_sum(n + 1, 0);
for (int i = 0; i < n; ++i)
prefix_sum[i+1] = prefix_sum[i] + nums[i];
vector<vector<int>> dp(n+1, vector<int>(k+2, INT_MAX));
dp[0][0] = 0;
for (int i = 1; i <= n; ++i) {
for (int resizes = 1; resizes <= k+1; ++resizes) {
int max_num = 0;
for (int j = i-1; j >= 0; --j) {
max_num = max(max_num, nums[j]);
int segment_sum = prefix_sum[i] - prefix_sum[j];
int wasted = max_num * (i - j) - segment_sum;
if (dp[j][resizes-1] != INT_MAX)
dp[i][resizes] = min(dp[i][resizes], dp[j][resizes-1] + wasted);
}
}
}
int ans = INT_MAX;
for (int resizes = 1; resizes <= k+1; ++resizes)
ans = min(ans, dp[n][resizes]);
return ans;
}
};
import java.util.*;
class Solution {
public int minSpaceWastedKResizing(int[] nums, int k) {
int n = nums.length;
int[] prefixSum = new int[n+1];
for (int i = 0; i < n; ++i)
prefixSum[i+1] = prefixSum[i] + nums[i];
int[][] dp = new int[n+1][k+2];
for (int[] row : dp)
Arrays.fill(row, Integer.MAX_VALUE);
dp[0][0] = 0;
for (int i = 1; i <= n; ++i) {
for (int resizes = 1; resizes <= k+1; ++resizes) {
int maxNum = 0;
for (int j = i-1; j >= 0; --j) {
maxNum = Math.max(maxNum, nums[j]);
int segmentSum = prefixSum[i] - prefixSum[j];
int wasted = maxNum * (i - j) - segmentSum;
if (dp[j][resizes-1] != Integer.MAX_VALUE)
dp[i][resizes] = Math.min(dp[i][resizes], dp[j][resizes-1] + wasted);
}
}
}
int ans = Integer.MAX_VALUE;
for (int resizes = 1; resizes <= k+1; ++resizes)
ans = Math.min(ans, dp[n][resizes]);
return ans;
}
}
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var minSpaceWastedKResizing = function(nums, k) {
const n = nums.length;
const prefixSum = Array(n+1).fill(0);
for (let i = 0; i < n; ++i)
prefixSum[i+1] = prefixSum[i] + nums[i];
const dp = Array.from({length: n+1}, () => Array(k+2).fill(Infinity));
dp[0][0] = 0;
for (let i = 1; i <= n; ++i) {
for (let resizes = 1; resizes <= k+1; ++resizes) {
let maxNum = 0;
for (let j = i-1; j >= 0; --j) {
maxNum = Math.max(maxNum, nums[j]);
const segmentSum = prefixSum[i] - prefixSum[j];
const wasted = maxNum * (i - j) - segmentSum;
if (dp[j][resizes-1] !== Infinity)
dp[i][resizes] = Math.min(dp[i][resizes], dp[j][resizes-1] + wasted);
}
}
}
let ans = Infinity;
for (let resizes = 1; resizes <= k+1; ++resizes)
ans = Math.min(ans, dp[n][resizes]);
return ans;
};