Skip to content

2547. Minimum Cost to Split an Array 👍

  • Time: $O(n^2)$
  • Space: $O(n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
 public:
  int minCost(vector<int>& nums, int k) {
    constexpr int kMax = 1001;
    const int n = nums.size();
    // trimmedLength[i][j] := trimmed(nums[i..j]).length
    vector<vector<int>> trimmedLength(n, vector<int>(n));
    // dp[i] := the minimum cost to split nums[i..n)
    vector<int> dp(n + 1, INT_MAX / 2);

    for (int i = 0; i < n; ++i) {
      int length = 0;
      vector<int> count(kMax);
      for (int j = i; j < n; ++j) {
        if (++count[nums[j]] == 2)
          length += 2;
        else if (count[nums[j]] > 2)
          ++length;
        trimmedLength[i][j] = length;
      }
    }

    dp[n] = 0;

    for (int i = n - 1; i >= 0; --i)
      for (int j = i; j < n; ++j)
        dp[i] = min(dp[i], k + trimmedLength[i][j] + dp[j + 1]);

    return dp[0];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
  public int minCost(int[] nums, int k) {
    final int MAX = 1001;
    final int n = nums.length;
    // trimmedLength[i][j] := trimmed(nums[i..j]).length
    int[][] trimmedLength = new int[n][n];
    // dp[i] := the minimum cost to split nums[i..n)
    int[] dp = new int[n + 1];
    Arrays.fill(dp, Integer.MAX_VALUE / 2);

    for (int i = 0; i < n; ++i) {
      int length = 0;
      int[] count = new int[MAX];
      for (int j = i; j < n; ++j) {
        if (++count[nums[j]] == 2)
          length += 2;
        else if (count[nums[j]] > 2)
          ++length;
        trimmedLength[i][j] = length;
      }
    }

    dp[n] = 0;

    for (int i = n - 1; i >= 0; --i)
      for (int j = i; j < n; ++j)
        dp[i] = Math.min(dp[i], k + trimmedLength[i][j] + dp[j + 1]);

    return dp[0];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
  def minCost(self, nums: list[int], k: int) -> int:
    MAX = 1001
    n = len(nums)
    # trimmedLength[i][j] := trimmed(nums[i..j]).length
    trimmedLength = [[0] * n for _ in range(n)]
    # dp[i] := the minimum cost to split nums[i..n)
    dp = [math.inf] * n + [0]

    for i in range(n):
      length = 0
      count = [0] * MAX
      for j in range(i, n):
        count[nums[j]] += 1
        if count[nums[j]] == 2:
          length += 2
        elif count[nums[j]] > 2:
          length += 1
        trimmedLength[i][j] = length

    dp[n] = 0

    for i in range(n - 1, -1, -1):
      for j in range(i, n):
        dp[i] = min(dp[i], k + trimmedLength[i][j] + dp[j + 1])

    return dp[0]