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 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 <= 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 <= 2001 <= nums[i] <= 1060 <= k <= nums.length - 1
Companies:
Media.net
Related Topics:
Array, Dynamic Programming
First, consider the case where we can't use any resize. The array must be initialized with size max(A, i, j), where max(A, i, j) = max( A[i], A[i+1], ..., A[j] ).
Let wasted[i][j] be the min space wasted on A[i..j] without any resize. (0 <= i <= j < N)
wasted[i][j] = max(A, i, j) * (j - i + 1) - sum(A, i, j)
where max(A, i, j) = max(A[i], A[i+1], ..., A[j]) and sum(A, i, j) = A[i] + A[i+1] + ... + A[j]
Now, consider the normal case:
Let dp[k][i+1] be the min space wasted on A[0..i] and k resize used (0 <= i < N, 0 <= k <= K)
For k = 0 and 0 <= i < N, dp[0][i+1] = wasted[0][i]
For 1 <= k <= K and 0 <= i < N:
dp[k][i+1] = min( dp[k-1][t] + wasted[t][i] | 0 <= t <= i )
dp[k][0] = 0
The answer is dp[K][N].
// OJ: https://leetcode.com/problems/minimum-total-space-wasted-with-k-resizing-operations/
// Author: github.com/lzl124631x
// Time: O(N^2 * K)
// Space: O(N^2 + NK)
class Solution {
public:
int minSpaceWastedKResizing(vector<int>& A, int K) {
int N = A.size(), wasted[201][201] = {}, dp[201][201] = {};
memset(dp, 0x3f, sizeof(dp));
for (int i = 0; i < N; ++i) {
int mx = 0, sum = 0;
for (int j = i; j < N; ++j) {
mx = max(mx, A[j]);
sum += A[j];
wasted[i][j] = mx * (j - i + 1) - sum;
}
dp[0][i + 1] = wasted[0][i];
}
for (int k = 0; k <= K; ++k) dp[k][0] = 0;
for (int k = 1; k <= K; ++k) {
for (int i = 0; i < N; ++i) {
for (int t = 0; t <= i; ++t) {
dp[k][i + 1] = min(dp[k][i + 1], dp[k - 1][t] + wasted[t][i]);
}
}
}
return dp[K][N];
}
};Since dp[k][i+1] only depends on value in the previous row, we can reduce space of dp from O(NK) to O(N).
// OJ: https://leetcode.com/problems/minimum-total-space-wasted-with-k-resizing-operations/
// Author: github.com/lzl124631x
// Time: O(N^2 * K)
// Space: O(N^2)
class Solution {
public:
int minSpaceWastedKResizing(vector<int>& A, int K) {
int N = A.size(), wasted[201][201] = {}, dp[201] = {};
for (int i = 0; i < N; ++i) {
int mx = 0, sum = 0;
for (int j = i; j < N; ++j) {
mx = max(mx, A[j]);
sum += A[j];
wasted[i][j] = mx * (j - i + 1) - sum;
}
dp[i + 1] = wasted[0][i];
}
for (int k = 1; k <= K; ++k) {
for (int i = N - 1; i >= 0; --i) {
for (int t = i; t >= 0; --t) {
dp[i + 1] = min(dp[i + 1], dp[t] + wasted[t][i]);
}
}
}
return dp[N];
}
};Also, we can calculate wasted values on the fly to save space.
// OJ: https://leetcode.com/problems/minimum-total-space-wasted-with-k-resizing-operations/
// Author: github.com/lzl124631x
// Time: O(N^2 * K)
// Space: O(N)
class Solution {
public:
int minSpaceWastedKResizing(vector<int>& A, int K) {
int N = A.size(), dp[201] = {};
for (int k = 0; k <= K; ++k) {
for (int i = N - 1; i >= 0; --i) {
int mx = 0, sum = 0, wasted = 0;
for (int t = i; t >= 0; --t) {
mx = max(mx, A[t]);
sum += A[t];
wasted = mx * (i - t + 1) - sum;
if (k > 0) dp[i + 1] = min(dp[i + 1], dp[t] + wasted);
}
if (k == 0) dp[i + 1] = wasted;
}
}
return dp[N];
}
};Let dp[i][k] be the min space wasted on A[i..(N-1)] and k resizes available.
// OJ: https://leetcode.com/problems/minimum-total-space-wasted-with-k-resizing-operations/
// Author: github.com/lzl124631x
// Time: O(N^2 * K)
// Space: O(NK)
class Solution {
int m[201][201] = {}, N, INF = 0x3f3f3f3f;
int dp(vector<int> &A, int i, int k) {
if (i == N) return 0;
if (k < 0) return INF;
if (m[i][k] != -1) return m[i][k];
int mx = 0, sum = 0, val = INF;
for (int j = i; j < N; ++j) {
mx = max(mx, A[j]);
sum += A[j];
int wasted = mx * (j - i + 1) - sum;
val = min(val, wasted + dp(A, j + 1, k - 1));
}
return m[i][k] = val;
}
public:
int minSpaceWastedKResizing(vector<int>& A, int k) {
N = A.size();
memset(m, -1, sizeof(m));
return dp(A, 0, k);
}
};Or let dp[i][k] be the min space wasted on A[0..(i-1)] and k resizes available
// OJ: https://leetcode.com/problems/minimum-total-space-wasted-with-k-resizing-operations/
// Author: github.com/lzl124631x
// Time: O(N^2 * K)
// Space: O(NK)
class Solution {
int m[201][201] = {}, N, INF = 0x3f3f3f3f;
int dp(vector<int> &A, int i, int k) {
if (i == 0) return 0;
if (k < 0) return INF;
if (m[i][k] != -1) return m[i][k];
int mx = 0, sum = 0, val = INF;
for (int j = i - 1; j >= 0; --j) {
mx = max(mx, A[j]);
sum += A[j];
int wasted = mx * (i - j) - sum;
val = min(val, dp(A, j, k - 1) + wasted);
}
return m[i][k] = val;
}
public:
int minSpaceWastedKResizing(vector<int>& A, int k) {
N = A.size();
memset(m, -1, sizeof(m));
return dp(A, N, k);
}
};