LeetCode 2547: Minimum Cost to Split an Array
Problem Description
Explanation
To solve this problem, we can use dynamic programming. We will create a 2D DP array where dp[i][j] represents the minimum cost to split the subarray nums[0:i] into j parts.
At each index i, we can either split the subarray at this index or extend the previous split. We will iterate over all possible split points and calculate the cost accordingly. To determine the cost, we need to calculate the trimmed version of the subarray and add the importance value.
The trimmed version of a subarray can be obtained by removing elements that appear only once. The importance value of a subarray is k + trimmed(subarray).length.
Finally, the minimum cost to split the entire array into some number of non-empty subarrays will be the minimum cost from dp[nums.length][1] to dp[nums.length][nums.length].
Time complexity: O(n^3) where n is the length of the input array nums. Space complexity: O(n^2)
Solutions
class Solution {
public int minCost(int[] nums, int k) {
int n = nums.length;
int[][] dp = new int[n + 1][n + 1];
for (int i = 1; i <= n; i++) {
dp[i][1] = calculateCost(nums, 0, i - 1, k);
for (int j = 2; j <= i; j++) {
dp[i][j] = Integer.MAX_VALUE;
for (int x = 0; x < i; x++) {
dp[i][j] = Math.min(dp[i][j], dp[x][j - 1] + calculateCost(nums, x, i - 1, k));
}
}
}
int minCost = Integer.MAX_VALUE;
for (int j = 1; j <= n; j++) {
minCost = Math.min(minCost, dp[n][j]);
}
return minCost;
}
private int calculateCost(int[] nums, int start, int end, int k) {
int[] freq = new int[n + 1];
for (int i = start; i <= end; i++) {
freq[nums[i]]++;
}
int trimmedLength = 0;
for (int i = start; i <= end; i++) {
if (freq[nums[i]] > 1) {
trimmedLength++;
}
}
return k + trimmedLength;
}
}Loading editor...