Skip to main content
Back to problems
#3500
Hard Algorithms

Minimum cost to divide array into subarrays

Array Dynamic Programming Prefix Sum
27.6% acceptance
Feb 25, 2026
84
11
You are given two integer arrays, nums and cost, of the same size, and an integer k. You can divide nums into subarrays. The cost of the ith subarray consisting of elements nums[l..r] is: (nums[0] + nums[1] + ... + nums[r] + k * i) * (cost[l] + cost[l + 1] + ... + cost[r]). Note that i represents the order of the subarray: 1 for the first subarray, 2 for the second, and so on. Return the minimum total cost possible from any valid division.

Solution

Rust
Time O(n^2)
Space O(n)
LeetCode
solution.rs 
impl Solution {
  pub fn minimum_cost(nums: Vec<i32>, cost: Vec<i32>, k: i32) -> i64 {
    // Key insight: for a partition into subarrays at split points s_1 < s_2 < ... < s_{m-1} < n,
    // sum_t t * C_t  =  m * Q[n]  -  sum_{t=1}^{m-1} Q[s_t]
    // where Q[i] = prefix_cost[i] and C_t is the cost-sum of the t-th subarray.
    //
    // This lets us remove the subarray-count from the DP state:
    //   dp[0] = 0
    //   dp[i] (i < n): min over j<i of  dp[j] + P[i]*(Q[i]-Q[j]) + k*(Q[n]-Q[i])
    //   dp[n]:          min over j<n of  dp[j] + P[n]*(Q[n]-Q[j]) + k*Q[n]
    // O(n^2) time, O(n) space.
    let n = nums.len();
    let k = k as i64;
    let mut p = vec![0i64; n + 1]; // prefix sums of nums
    let mut q = vec![0i64; n + 1]; // prefix sums of cost
    for i in 0..n {
      p[i + 1] = p[i] + nums[i] as i64;
      q[i + 1] = q[i] + cost[i] as i64;
    }
    let qn = q[n];
    let mut dp = vec![i64::MAX / 2; n + 1];
    dp[0] = 0;
    for i in 1..=n {
      for j in 0..i {
        if dp[j] == i64::MAX / 2 { continue; }
        let val = if i < n {
          dp[j] + p[i] * (q[i] - q[j]) + k * (qn - q[i])
        } else {
          dp[j] + p[n] * (qn - q[j]) + k * qn
        };
        if val < dp[i] { dp[i] = val; }
      }
    }
    dp[n]
  }
}