# Minimum Cost to Divide Array Into Subarrays
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-cost-to-divide-array-into-subarrays)
Canonical: https://scaleengineer.com/dsa/problems/minimum-cost-to-divide-array-into-subarrays
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array
---
## 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:**

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

# Approaches
## Dynamic Programming (TLE)
A straightforward approach to this problem is using dynamic programming. We can define a DP state `dp[i][m]` as the minimum cost to partition the first `i` elements of the `nums` array into exactly `m` subarrays. To compute `dp[i][m]`, we can try all possible split points `j` for the last subarray. If the last subarray is `nums[j...i-1]`, then the first `j` elements must have been optimally partitioned into `m-1` subarrays. This leads to a recurrence relation involving three nested loops, resulting in a cubic time complexity.
**Time:** O(N^3) due to three nested loops for `m`, `i`, and `j`. · **Space:** O(N^2) to store the DP table.
**Pros:** Relatively simple to understand and derive.; Correctly models the problem's state transitions.
**Cons:** The time complexity of O(N^3) is too high for the given constraints (N <= 1000), leading to a Time Limit Exceeded (TLE) error on most platforms.
### Explanation
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:
`dp[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.

```java
import java.util.Arrays;

class Solution {
    public long minimumCost(int[] nums, int[] cost, int k) {
        int n = nums.length;
        long[] prefixNums = new long[n + 1];
        long[] prefixCost = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefixNums[i + 1] = prefixNums[i] + nums[i];
            prefixCost[i + 1] = prefixCost[i] + cost[i];
        }

        long[][] dp = new long[n + 1][n + 1];
        for (long[] row : dp) {
            Arrays.fill(row, Long.MAX_VALUE / 2);
        }
        dp[0][0] = 0;

        for (int m = 1; m <= n; m++) { // Number of subarrays
            for (int i = m; i <= n; i++) { // End index of the prefix (exclusive)
                for (int j = m - 1; j < i; j++) { // Split point
                    long lastSubarrayCost = (prefixNums[i] + (long)k * m) * (prefixCost[i] - prefixCost[j]);
                    if (dp[j][m - 1] != Long.MAX_VALUE / 2) {
                        dp[i][m] = Math.min(dp[i][m], dp[j][m - 1] + lastSubarrayCost);
                    }
                }
            }
        }

        long minTotalCost = Long.MAX_VALUE;
        for (int m = 1; m <= n; m++) {
            minTotalCost = Math.min(minTotalCost, dp[n][m]);
        }

        return minTotalCost;
    }
}
```
### Algorithm
- 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`.

## Dynamic Programming with Convex Hull Trick
The `O(N^3)` DP solution can be optimized by observing the structure of its recurrence. After rearranging the terms, the inner loop that finds the minimum value can be seen as a set of line queries. Specifically, we are trying to find `min(C_j - M_j * x_i)`, where `C_j` and `M_j` depend on the split point `j`, and `x_i` depends on the current index `i`. This structure is a perfect fit for the Convex Hull Trick (CHT) optimization. By maintaining the lower envelope of these lines using a deque, we can perform the minimization step in amortized constant time, reducing the overall complexity from `O(N^3)` to `O(N^2)`.
**Time:** O(N^2). The two outer loops run N times each. The inner CHT operations (deque manipulations) take amortized O(1) time. · **Space:** O(N^2) for the DP table, which can be optimized to O(N) by only storing the DP values for the previous number of partitions.
**Pros:** Efficient enough to pass within the time limits.; Reduces time complexity from cubic to quadratic.; Can be space-optimized to O(N).
**Cons:** Significantly more complex to understand and implement correctly compared to the naive DP.; Requires knowledge of Convex Hull Trick optimization.
### Explanation
The key to optimization lies in the recurrence relation:
`dp[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:
`dp[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.

```java
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

class Solution {
    // Represents a line y = mx + c
    static class Line {
        long m, c;
        Line(long m, long c) {
            this.m = m;
            this.c = c;
        }
        long eval(long x) {
            return m * x + c;
        }
    }

    // Using cross-product to avoid floating point issues
    private boolean isRedundant(Line l1, Line l2, Line l3) {
        // (c3 - c1) * (m1 - m2) <= (c2 - c1) * (m1 - m3)
        return (l3.c - l1.c) * (l1.m - l2.m) <= (l2.c - l1.c) * (l1.m - l3.m);
    }

    public long minimumCost(int[] nums, int[] cost, int k) {
        int n = nums.length;
        long[] prefixNums = new long[n + 1];
        long[] prefixCost = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefixNums[i + 1] = prefixNums[i] + nums[i];
            prefixCost[i + 1] = prefixCost[i] + cost[i];
        }

        long[] dpPrev = new long[n + 1];
        Arrays.fill(dpPrev, Long.MAX_VALUE / 2);
        dpPrev[0] = 0;

        long minTotalCost = Long.MAX_VALUE;

        for (int m = 1; m <= n; m++) { // Number of subarrays
            long[] dpCurr = new long[n + 1];
            Arrays.fill(dpCurr, Long.MAX_VALUE / 2);
            Deque<Line> deque = new ArrayDeque<>();

            for (int i = m; i <= n; i++) {
                // Add line for split point j = i - 1
                // Line is based on dpPrev, i.e., m-1 partitions
                if (dpPrev[i - 1] != Long.MAX_VALUE / 2) {
                    Line newLine = new Line(-prefixCost[i - 1], dpPrev[i - 1]);
                    while (deque.size() >= 2 && isRedundant(deque.get(deque.size() - 2), deque.getLast(), newLine)) {
                        deque.removeLast();
                    }
                    deque.addLast(newLine);
                }

                // Query for current i
                if (!deque.isEmpty()) {
                    long x = prefixNums[i] + (long)k * m;
                    while (deque.size() >= 2 && deque.getFirst().eval(x) >= deque.get(1).eval(x)) {
                        deque.removeFirst();
                    }
                    long minVal = deque.getFirst().eval(x);
                    dpCurr[i] = x * prefixCost[i] + minVal;
                }
            }
            minTotalCost = Math.min(minTotalCost, dpCurr[n]);
            dpPrev = dpCurr;
        }

        return minTotalCost;
    }
}
```
### Algorithm
- 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`:
  `dp[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)`.