Welcome to Subscribe On Youtube
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 <= 2001 <= nums[i] <= 10^60 <= 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]; } } ############ class Solution { public int minSpaceWastedKResizing(int[] nums, int k) { ++k; int n = nums.length; int[][] g = new int[n][n]; for (int i = 0; i < n; ++i) { int s = 0, mx = 0; for (int j = i; j < n; ++j) { s += nums[j]; mx = Math.max(mx, nums[j]); g[i][j] = mx * (j - i + 1) - s; } } int[][] f = new int[n + 1][k + 1]; int inf = 0x3f3f3f3f; for (int i = 0; i < f.length; ++i) { Arrays.fill(f[i], inf); } f[0][0] = 0; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= k; ++j) { for (int h = 0; h < i; ++h) { f[i][j] = Math.min(f[i][j], f[h][j - 1] + g[h][i - 1]); } } } return f[n][k]; } } -
// OJ: https://leetcode.com/problems/minimum-total-space-wasted-with-k-resizing-operations/ // 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]; } }; -
class Solution: def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int: k += 1 n = len(nums) g = [[0] * n for _ in range(n)] for i in range(n): s = mx = 0 for j in range(i, n): s += nums[j] mx = max(mx, nums[j]) g[i][j] = mx * (j - i + 1) - s f = [[inf] * (k + 1) for _ in range(n + 1)] f[0][0] = 0 for i in range(1, n + 1): for j in range(1, k + 1): for h in range(i): f[i][j] = min(f[i][j], f[h][j - 1] + g[h][i - 1]) return f[-1][-1] -
func minSpaceWastedKResizing(nums []int, k int) int { k++ n := len(nums) g := make([][]int, n) for i := range g { g[i] = make([]int, n) } for i := 0; i < n; i++ { s, mx := 0, 0 for j := i; j < n; j++ { s += nums[j] mx = max(mx, nums[j]) g[i][j] = mx*(j-i+1) - s } } f := make([][]int, n+1) inf := 0x3f3f3f3f for i := range f { f[i] = make([]int, k+1) for j := range f[i] { f[i][j] = inf } } f[0][0] = 0 for i := 1; i <= n; i++ { for j := 1; j <= k; j++ { for h := 0; h < i; h++ { f[i][j] = min(f[i][j], f[h][j-1]+g[h][i-1]) } } } return f[n][k] } func max(a, b int) int { if a > b { return a } return b } func min(a, b int) int { if a < b { return a } return b }