Skip to content

3500. Minimum Cost to Divide Array Into Subarrays 👍

  • Time: $O(n^2)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  long long minimumCost(vector<int>& nums, vector<int>& cost, int k) {
    const int n = nums.size();
    vector<long> prefixNums(n + 1);
    vector<long> prefixCost(n + 1);
    // dp[i] := the minimum cost to divide nums[i..n - 1] into subarrays
    vector<long> dp(n + 1, LONG_MAX);

    partial_sum(nums.begin(), nums.end(), prefixNums.begin() + 1);
    partial_sum(cost.begin(), cost.end(), prefixCost.begin() + 1);
    dp[n] = 0;

    for (int i = n - 1; i >= 0; --i)
      for (int j = i; j < n; ++j)
        dp[i] =
            min(dp[i], prefixNums[j + 1] * (prefixCost[j + 1] - prefixCost[i]) +
                           k * (prefixCost[n] - prefixCost[i]) + 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
class Solution {
  public long minimumCost(int[] nums, int[] cost, int k) {
    final int n = nums.length;
    long[] prefixNums = new long[n + 1];
    long[] prefixCost = new long[n + 1];
    // dp[i] := the minimum cost to divide nums[i..n - 1] into subarrays
    long[] dp = new long[n + 1];

    for (int i = 0; i < n; ++i) {
      prefixNums[i + 1] = prefixNums[i] + nums[i];
      prefixCost[i + 1] = prefixCost[i] + cost[i];
    }

    Arrays.fill(dp, Long.MAX_VALUE);
    dp[n] = 0;

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

    return dp[0];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
  def minimumCost(self, nums: list[int], cost: list[int], k: int) -> int:
    n = len(nums)
    prefixNums = list(itertools.accumulate(nums, initial=0))
    prefixCost = list(itertools.accumulate(cost, initial=0))
    # dp[i] := the minimum cost to divide nums[i..n - 1] into subarrays
    dp = [math.inf] * n + [0]

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

    return dp[0]