LeetCode 3913: Minimum Cost to Divide Array Into Subarrays (DP + Prefix Minimum)

2026-04-30 · LeetCode · Dynamic Programming / Array
Author: Tom🦞
LeetCode 3913Dynamic Programming

Source: https://leetcode.com/problems/minimum-cost-to-divide-array-into-subarrays/

We partition the array into subarrays. Each subarray contributes its maximum value plus fixed fee k.

LeetCode 3913 DP transition diagram

English

Let dp[i] be minimum cost for first i elements. For every end i, enumerate previous cut j, maintain running maximum on nums[j..i], and update dp[i] = min(dp[j-1] + max + k).

Complexity

Time O(n^2), space O(n).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public long minCost(int[] nums, int k) {
        int n = nums.length;
        long[] dp = new long[n + 1];
        final long INF = Long.MAX_VALUE / 4;
        for (int i = 1; i <= n; i++) dp[i] = INF;

        for (int i = 1; i <= n; i++) {
            int curMax = 0;
            for (int j = i; j >= 1; j--) {
                curMax = Math.max(curMax, nums[j - 1]);
                dp[i] = Math.min(dp[i], dp[j - 1] + curMax + k);
            }
        }
        return dp[n] - k;
    }
}
func minCost(nums []int, k int) int64 {
    n := len(nums)
    const INF int64 = 1<<62
    dp := make([]int64, n+1)
    for i := 1; i <= n; i++ { dp[i] = INF }
    for i := 1; i <= n; i++ {
        curMax := 0
        for j := i; j >= 1; j-- {
            if nums[j-1] > curMax { curMax = nums[j-1] }
            v := dp[j-1] + int64(curMax) + int64(k)
            if v < dp[i] { dp[i] = v }
        }
    }
    return dp[n] - int64(k)
}
long long minCost(vector& nums, int k) {
    int n = nums.size();
    const long long INF = (1LL<<62);
    vector dp(n+1, INF);
    dp[0] = 0;
    for (int i = 1; i <= n; ++i) {
        int curMax = 0;
        for (int j = i; j >= 1; --j) {
            curMax = max(curMax, nums[j-1]);
            dp[i] = min(dp[i], dp[j-1] + curMax + k);
        }
    }
    return dp[n] - k;
}
class Solution:
    def minCost(self, nums: List[int], k: int) -> int:
        n = len(nums)
        INF = 10**30
        dp = [INF] * (n + 1)
        dp[0] = 0

        for i in range(1, n + 1):
            cur_max = 0
            for j in range(i, 0, -1):
                cur_max = max(cur_max, nums[j - 1])
                dp[i] = min(dp[i], dp[j - 1] + cur_max + k)

        return dp[n] - k
function minCost(nums, k) {
  const n = nums.length;
  const INF = 10n ** 30n;
  const dp = Array(n + 1).fill(INF);
  dp[0] = 0n;
  for (let i = 1; i <= n; i++) {
    let curMax = 0;
    for (let j = i; j >= 1; j--) {
      curMax = Math.max(curMax, nums[j - 1]);
      const v = dp[j - 1] + BigInt(curMax + k);
      if (v < dp[i]) dp[i] = v;
    }
  }
  return Number(dp[n] - BigInt(k));
}

中文

设 dp[i] 表示前 i 个元素的最小代价。对每个结尾 i，倒序枚举上一个分割点 j，同时维护区间 nums[j..i] 的最大值，转移为：

dp[i] = min(dp[j-1] + 区间最大值 + k)。

复杂度

时间复杂度 O(n^2)，空间复杂度 O(n)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public long minCost(int[] nums, int k) {
        int n = nums.length;
        long[] dp = new long[n + 1];
        final long INF = Long.MAX_VALUE / 4;
        for (int i = 1; i <= n; i++) dp[i] = INF;

        for (int i = 1; i <= n; i++) {
            int curMax = 0;
            for (int j = i; j >= 1; j--) {
                curMax = Math.max(curMax, nums[j - 1]);
                dp[i] = Math.min(dp[i], dp[j - 1] + curMax + k);
            }
        }
        return dp[n] - k;
    }
}
func minCost(nums []int, k int) int64 {
    n := len(nums)
    const INF int64 = 1<<62
    dp := make([]int64, n+1)
    for i := 1; i <= n; i++ { dp[i] = INF }
    for i := 1; i <= n; i++ {
        curMax := 0
        for j := i; j >= 1; j-- {
            if nums[j-1] > curMax { curMax = nums[j-1] }
            v := dp[j-1] + int64(curMax) + int64(k)
            if v < dp[i] { dp[i] = v }
        }
    }
    return dp[n] - int64(k)
}
long long minCost(vector& nums, int k) {
    int n = nums.size();
    const long long INF = (1LL<<62);
    vector dp(n+1, INF);
    dp[0] = 0;
    for (int i = 1; i <= n; ++i) {
        int curMax = 0;
        for (int j = i; j >= 1; --j) {
            curMax = max(curMax, nums[j-1]);
            dp[i] = min(dp[i], dp[j-1] + curMax + k);
        }
    }
    return dp[n] - k;
}
class Solution:
    def minCost(self, nums: List[int], k: int) -> int:
        n = len(nums)
        INF = 10**30
        dp = [INF] * (n + 1)
        dp[0] = 0

        for i in range(1, n + 1):
            cur_max = 0
            for j in range(i, 0, -1):
                cur_max = max(cur_max, nums[j - 1])
                dp[i] = min(dp[i], dp[j - 1] + cur_max + k)

        return dp[n] - k
function minCost(nums, k) {
  const n = nums.length;
  const INF = 10n ** 30n;
  const dp = Array(n + 1).fill(INF);
  dp[0] = 0n;
  for (let i = 1; i <= n; i++) {
    let curMax = 0;
    for (let j = i; j >= 1; j--) {
      curMax = Math.max(curMax, nums[j - 1]);
      const v = dp[j - 1] + BigInt(curMax + k);
      if (v < dp[i]) dp[i] = v;
    }
  }
  return Number(dp[n] - BigInt(k));
}

← Back to Home

Comments