Minimum Cost to Divide Array Into Subarrays
HardUpdated: Aug 2, 2025
Practice on:
Problem
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.
Examples
Example 1
Input: nums = [3,1,4], cost = [4,6,6], k = 1
Output: 110
Explanation:
The minimum total cost possible can be achieved by dividing `nums` into
subarrays `[3, 1]` and `[4]`.
* The cost of the first subarray `[3,1]` is `(3 + 1 + 1 * 1) * (4 + 6) = 50`.
* The cost of the second subarray `[4]` is `(3 + 1 + 4 + 1 * 2) * 6 = 60`.
Example 2
Input: nums = [4,8,5,1,14,2,2,12,1], cost = [7,2,8,4,2,2,1,1,2], k = 7
Output: 985
Explanation:
The minimum total cost possible can be achieved by dividing `nums` into
subarrays `[4, 8, 5, 1]`, `[14, 2, 2]`, and `[12, 1]`.
* The cost of the first subarray `[4, 8, 5, 1]` is `(4 + 8 + 5 + 1 + 7 * 1) * (7 + 2 + 8 + 4) = 525`.
* The cost of the second subarray `[14, 2, 2]` is `(4 + 8 + 5 + 1 + 14 + 2 + 2 + 7 * 2) * (2 + 2 + 1) = 250`.
* The cost of the third subarray `[12, 1]` is `(4 + 8 + 5 + 1 + 14 + 2 + 2 + 12 + 1 + 7 * 3) * (1 + 2) = 210`.
Constraints
1 <= nums.length <= 1000cost.length == nums.length1 <= nums[i], cost[i] <= 10001 <= k <= 1000
Solution
Method 1 – Dynamic Programming (Prefix Sum Optimization)
Intuition
We want to divide the array into subarrays to minimize the total cost, where each subarray's cost depends on the sum of its elements, the sum of its costs, and its order. The problem is similar to partitioning with DP, and prefix sums help us compute subarray sums efficiently.
Approach
- Compute prefix sums for
numsandcostto quickly get subarray sums. - Use DP:
dp[i]is the minimum cost to divide the firstielements. - For each position
i, try all possible previous split pointsj:- The cost for subarray
[j, i-1]is(sum(nums[0..i-1]) + k * part) * sum(cost[j..i-1]), wherepartis the current subarray's order. - Update
dp[i]as the minimum over all splits.
- The cost for subarray
- Return
dp[n]for the answer.
Code
C++
class Solution {
public:
long long minimumCost(vector<int>& nums, vector<int>& cost, int k) {
int n = nums.size();
vector<long long> psum(n+1), csum(n+1);
for (int i = 0; i < n; ++i) {
psum[i+1] = psum[i] + nums[i];
csum[i+1] = csum[i] + cost[i];
}
vector<long long> dp(n+1, LLONG_MAX);
dp[0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < i; ++j) {
int part = 1;
for (int t = j; t < i; ++t) part = 1 + (dp[j] != 0);
long long sub = psum[i] + k * part;
long long c = csum[i] - csum[j];
dp[i] = min(dp[i], dp[j] + sub * c);
}
}
return dp[n];
}
};
Go
func minimumCost(nums, cost []int, k int) int64 {
n := len(nums)
psum := make([]int64, n+1)
csum := make([]int64, n+1)
for i := 0; i < n; i++ {
psum[i+1] = psum[i] + int64(nums[i])
csum[i+1] = csum[i] + int64(cost[i])
}
dp := make([]int64, n+1)
for i := range dp { dp[i] = 1<<62 }
dp[0] = 0
for i := 1; i <= n; i++ {
for j := 0; j < i; j++ {
part := 1
if dp[j] != 0 { part = 2 }
sub := psum[i] + int64(k)*int64(part)
c := csum[i] - csum[j]
if v := dp[j] + sub*c; v < dp[i] { dp[i] = v }
}
}
return dp[n]
}
Java
class Solution {
public long minimumCost(int[] nums, int[] cost, int k) {
int n = nums.length;
long[] psum = new long[n+1], csum = new long[n+1];
for (int i = 0; i < n; ++i) {
psum[i+1] = psum[i] + nums[i];
csum[i+1] = csum[i] + cost[i];
}
long[] dp = new long[n+1];
Arrays.fill(dp, Long.MAX_VALUE);
dp[0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < i; ++j) {
int part = dp[j] == 0 ? 1 : 2;
long sub = psum[i] + k * part;
long c = csum[i] - csum[j];
dp[i] = Math.min(dp[i], dp[j] + sub * c);
}
}
return dp[n];
}
}
Kotlin
class Solution {
fun minimumCost(nums: IntArray, cost: IntArray, k: Int): Long {
val n = nums.size
val psum = LongArray(n+1)
val csum = LongArray(n+1)
for (i in 0 until n) {
psum[i+1] = psum[i] + nums[i]
csum[i+1] = csum[i] + cost[i]
}
val dp = LongArray(n+1) { Long.MAX_VALUE }
dp[0] = 0L
for (i in 1..n) {
for (j in 0 until i) {
val part = if (dp[j] == 0L) 1 else 2
val sub = psum[i] + k * part
val c = csum[i] - csum[j]
dp[i] = minOf(dp[i], dp[j] + sub * c)
}
}
return dp[n]
}
}
Python
class Solution:
def minimumCost(self, nums: list[int], cost: list[int], k: int) -> int:
n = len(nums)
psum = [0] * (n+1)
csum = [0] * (n+1)
for i in range(n):
psum[i+1] = psum[i] + nums[i]
csum[i+1] = csum[i] + cost[i]
dp = [float('inf')] * (n+1)
dp[0] = 0
for i in range(1, n+1):
for j in range(i):
part = 1 if dp[j] == 0 else 2
sub = psum[i] + k * part
c = csum[i] - csum[j]
dp[i] = min(dp[i], dp[j] + sub * c)
return dp[n]
Rust
impl Solution {
pub fn minimum_cost(nums: Vec<i32>, cost: Vec<i32>, k: i32) -> i64 {
let n = nums.len();
let mut psum = vec![0i64; n+1];
let mut csum = vec![0i64; n+1];
for i in 0..n {
psum[i+1] = psum[i] + nums[i] as i64;
csum[i+1] = csum[i] + cost[i] as i64;
}
let mut dp = vec![i64::MAX; n+1];
dp[0] = 0;
for i in 1..=n {
for j in 0..i {
let part = if dp[j] == 0 { 1 } else { 2 };
let sub = psum[i] + k as i64 * part;
let c = csum[i] - csum[j];
dp[i] = dp[i].min(dp[j] + sub * c);
}
}
dp[n]
}
}
TypeScript
class Solution {
minimumCost(nums: number[], cost: number[], k: number): number {
const n = nums.length;
const psum = Array(n+1).fill(0);
const csum = Array(n+1).fill(0);
for (let i = 0; i < n; ++i) {
psum[i+1] = psum[i] + nums[i];
csum[i+1] = csum[i] + cost[i];
}
const dp = Array(n+1).fill(Infinity);
dp[0] = 0;
for (let i = 1; i <= n; ++i) {
for (let j = 0; j < i; ++j) {
const part = dp[j] === 0 ? 1 : 2;
const sub = psum[i] + k * part;
const c = csum[i] - csum[j];
dp[i] = Math.min(dp[i], dp[j] + sub * c);
}
}
return dp[n];
}
}
Complexity
- ⏰ Time complexity:
O(n^2)where n is the length of the array, due to nested loops. - 🧺 Space complexity:
O(n)for prefix sums and DP array.