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.

Example 1

1
2
3
4
5
6
7

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

1
2
3
4
5
6
7
8

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 <= 1000
  • cost.length == nums.length
  • 1 <= nums[i], cost[i] <= 1000
  • 1 <= k <= 1000

Examples

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

  1. Compute prefix sums for nums and cost to quickly get subarray sums.
  2. Use DP: dp[i] is the minimum cost to divide the first i elements.
  3. For each position i, try all possible previous split points j:
    • The cost for subarray [j, i-1] is (sum(nums[0..i-1]) + k * part) * sum(cost[j..i-1]), where part is the current subarray’s order.
    • Update dp[i] as the minimum over all splits.
  4. Return dp[n] for the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

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]
}
 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 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];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

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]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

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]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

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.