Minimum Cost to Divide Array Into Subarrays

• Precompute prefix sums for nums and cost arrays, let's call them prefixNums and prefixCost respectively. This allows for O(1) range sum queries.
• Define a 2D DP table, dp[i][m], to store the minimum cost to partition the prefix nums[0...i-1] into exactly m subarrays.
• Initialize the dp table with a large value representing infinity. Set the base case dp[0][0] = 0.
• Iterate through the number of subarrays m from 1 to n.
• For each m, iterate through the end index of the prefix i from m to n.
• To compute dp[i][m], iterate through all possible split points j from m-1 to i-1. The last subarray would be nums[j...i-1].
• The cost of this partition is the optimal cost for nums[0...j-1] with m-1 subarrays (dp[j][m-1]) plus the cost of the new m-th subarray.
• The cost of the m-th subarray nums[j...i-1] is (prefixNums[i] + k * m) * (prefixCost[i] - prefixCost[j]).
• The recurrence relation is: dp[i][m] = min(dp[i][m], dp[j][m-1] + (prefixNums[i] + k * m) * (prefixCost[i] - prefixCost[j])).
• After filling the dp table, the minimum total cost is the minimum value in the last row of the dp table, i.e., min(dp[n][m]) for m from 1 to n.

Let's define dp[i][m] as the minimum cost to partition the prefix nums[0...i-1] into m subarrays. Our goal is to find the minimum of dp[n][m] over all possible numbers of subarrays m (from 1 to n).

To compute dp[i][m], we consider the last subarray in the partition. Suppose it starts at index j and ends at i-1. This means the prefix nums[0...j-1] was partitioned into m-1 subarrays. The minimum cost for that is dp[j][m-1]. The newly formed subarray nums[j...i-1] is the m-th subarray in the sequence.

The cost of this m-th subarray is given by the formula: (sum(nums[0...i-1]) + k * m) * sum(cost[j...i-1]).

To efficiently calculate the sums, we can precompute prefix sum arrays for both nums and cost. Let prefixNums[i] be the sum of the first i elements of nums, and prefixCost[i] be the sum of the first i elements of cost.

The recurrence relation becomes:

1dp[i][m] = min_{m-1 <= j < i} { dp[j][m-1] + (prefixNums[i] + k * m) * (prefixCost[i] - prefixCost[j]) }

The base case is dp[0][0] = 0, representing a cost of 0 to partition an empty prefix into 0 subarrays.

We iterate m from 1 to n, i from m to n, and j from m-1 to i-1. This three-level nested loop structure gives the O(N^3) complexity. All cost calculations should use long to prevent integer overflow.

1import java.util.Arrays;2 3class Solution {4    public long minimumCost(int[] nums, int[] cost, int k) {5        int n = nums.length;6        long[] prefixNums = new long[n + 1];7        long[] prefixCost = new long[n + 1];8        for (int i = 0; i < n; i++) {9            prefixNums[i + 1] = prefixNums[i] + nums[i];10            prefixCost[i + 1] = prefixCost[i] + cost[i];11        }12 13        long[][] dp = new long[n + 1][n + 1];14        for (long[] row : dp) {15            Arrays.fill(row, Long.MAX_VALUE / 2);16        }17        dp[0][0] = 0;18 19        for (int m = 1; m <= n; m++) { // Number of subarrays20            for (int i = m; i <= n; i++) { // End index of the prefix (exclusive)21                for (int j = m - 1; j < i; j++) { // Split point22                    long lastSubarrayCost = (prefixNums[i] + (long)k * m) * (prefixCost[i] - prefixCost[j]);23                    if (dp[j][m - 1] != Long.MAX_VALUE / 2) {24                        dp[i][m] = Math.min(dp[i][m], dp[j][m - 1] + lastSubarrayCost);25                    }26                }27            }28        }29 30        long minTotalCost = Long.MAX_VALUE;31        for (int m = 1; m <= n; m++) {32            minTotalCost = Math.min(minTotalCost, dp[n][m]);33        }34 35        return minTotalCost;36    }37}

• Use the same DP state dp[i][m] and prefix sums as the O(N^3) approach.
• Rearrange the recurrence relation to isolate the terms dependent on the inner loop variable j:

  1dp[i][m] = (prefixNums[i] + k*m) * prefixCost[i] + min_{m-1 <= j < i} { dp[j][m-1] - (prefixNums[i] + k*m) * prefixCost[j] }

• Recognize that the minimization part is equivalent to finding the minimum value of a set of linear functions. For each j, we have a line L_j(x) = M_j * x + C_j, where M_j = -prefixCost[j], C_j = dp[j][m-1], and we query it at x = prefixNums[i] + k*m.
• This is a classic Convex Hull Trick (CHT) problem. Since the slopes M_j are monotonically decreasing (as prefixCost[j] is increasing) and query points x are monotonically increasing (as prefixNums[i] is increasing), we can use a deque to maintain the lower envelope of the lines in amortized O(1) time per operation.
• For each m from 1 to n, we build the CHT structure for lines derived from dp[...][m-1] and query it to compute dp[...][m].
• The outer loop for m and the inner loop for i remain, but the innermost loop for j is replaced by amortized O(1) CHT operations.
• To optimize space, notice that computing dp[...][m] only requires dp[...][m-1]. We can use two 1D arrays (dp_prev, dp_curr) instead of a 2D table, reducing space to O(N).

The key to optimization lies in the recurrence relation:

1dp[i][m] = min_{m-1 <= j < i} { dp[j][m-1] + (prefixNums[i] + k*m) * (prefixCost[i] - prefixCost[j]) }

Let's expand and regroup the terms:

1dp[i][m] = (prefixNums[i] + k*m) * prefixCost[i] + min_{m-1 <= j < i} { dp[j][m-1] - (prefixNums[i] + k*m) * prefixCost[j] }

For a fixed m, as we iterate i, the term (prefixNums[i] + k*m) * prefixCost[i] is constant with respect to j. The challenge is the min part. Let x_i = prefixNums[i] + k*m. We need to find min_{j} { dp[j][m-1] - x_i * prefixCost[j] }.

This is equivalent to finding the minimum value among a set of lines. Each potential split point j defines a line L_j(x) = (-prefixCost[j]) * x + dp[j][m-1]. We want to find min_{j} L_j(x_i).

We can apply the Convex Hull Trick. For a fixed m, we iterate i from m to n. We need to query for x_i = prefixNums[i] + k*m. Since nums contains positive integers, prefixNums[i] is strictly increasing with i, so our query points x_i are monotonic. The slopes of our lines are M_j = -prefixCost[j]. Since cost contains positive integers, prefixCost[j] is strictly increasing, making the slopes M_j strictly decreasing.

This specific scenario (monotonic queries on lines with monotonic slopes) allows for a highly efficient CHT implementation using a double-ended queue (deque). The deque will store the lines that form the lower envelope (the set of lines that can be optimal).

For each m:

1. We use a 1D array dp_prev to hold the values of dp[...][m-1] and dp_curr for dp[...][m].
2. We initialize a deque to store Line objects (or just their slopes and intercepts).
3. We iterate i from m to n. In each iteration: a. We form a new line L_{i-1} from dp_prev[i-1] and prefixCost[i-1]. We add this line to our deque, maintaining the convex property by removing lines from the back of the deque that become redundant. b. We query the deque with x_i to find the optimal line. Since query points are increasing, we can remove lines from the front of the deque that are no longer optimal. c. We use the result of the query to compute dp_curr[i].
4. After the loop for i finishes, we find the minimum cost for m partitions, which is dp_curr[n], and update our overall answer. Then, we set dp_prev = dp_curr for the next iteration of m.

This process reduces the innermost loop to an amortized O(1) operation, making the total time complexity O(N^2) and space complexity O(N) with the space optimization.

1import java.util.ArrayDeque;2import java.util.Arrays;3import java.util.Deque;4 5class Solution {6    // Represents a line y = mx + c7    static class Line {8        long m, c;9        Line(long m, long c) {10            this.m = m;11            this.c = c;12        }13        long eval(long x) {14            return m * x + c;15        }16    }17 18    // Using cross-product to avoid floating point issues19    private boolean isRedundant(Line l1, Line l2, Line l3) {20        // (c3 - c1) * (m1 - m2) <= (c2 - c1) * (m1 - m3)21        return (l3.c - l1.c) * (l1.m - l2.m) <= (l2.c - l1.c) * (l1.m - l3.m);22    }23 24    public long minimumCost(int[] nums, int[] cost, int k) {25        int n = nums.length;26        long[] prefixNums = new long[n + 1];27        long[] prefixCost = new long[n + 1];28        for (int i = 0; i < n; i++) {29            prefixNums[i + 1] = prefixNums[i] + nums[i];30            prefixCost[i + 1] = prefixCost[i] + cost[i];31        }32 33        long[] dpPrev = new long[n + 1];34        Arrays.fill(dpPrev, Long.MAX_VALUE / 2);35        dpPrev[0] = 0;36 37        long minTotalCost = Long.MAX_VALUE;38 39        for (int m = 1; m <= n; m++) { // Number of subarrays40            long[] dpCurr = new long[n + 1];41            Arrays.fill(dpCurr, Long.MAX_VALUE / 2);42            Deque<Line> deque = new ArrayDeque<>();43 44            for (int i = m; i <= n; i++) {45                // Add line for split point j = i - 146                // Line is based on dpPrev, i.e., m-1 partitions47                if (dpPrev[i - 1] != Long.MAX_VALUE / 2) {48                    Line newLine = new Line(-prefixCost[i - 1], dpPrev[i - 1]);49                    while (deque.size() >= 2 && isRedundant(deque.get(deque.size() - 2), deque.getLast(), newLine)) {50                        deque.removeLast();51                    }52                    deque.addLast(newLine);53                }54 55                // Query for current i56                if (!deque.isEmpty()) {57                    long x = prefixNums[i] + (long)k * m;58                    while (deque.size() >= 2 && deque.getFirst().eval(x) >= deque.get(1).eval(x)) {59                        deque.removeFirst();60                    }61                    long minVal = deque.getFirst().eval(x);62                    dpCurr[i] = x * prefixCost[i] + minVal;63                }64            }65            minTotalCost = Math.min(minTotalCost, dpCurr[n]);66            dpPrev = dpCurr;67        }68 69        return minTotalCost;70    }71}