Minimum Cost to Divide Array Into Subarrays - Solution & Explanation

Problem Overview: You are given an array and must split it into multiple contiguous subarrays so the total cost of all chosen segments is minimized. The challenge is deciding where to place partition boundaries while computing subarray costs efficiently.

Approach 1: Brute Force Partition Enumeration (O(n^3) time, O(1) space)

The naive strategy tries every possible way to split the array. For each starting index i, iterate over all possible ending indices j to form a subarray, compute its cost directly by scanning the elements, and recursively evaluate the remaining suffix. Because computing each subarray cost may take O(n) and there are O(n^2) candidate segments, the total runtime grows to O(n^3). This approach is mainly useful for understanding the structure of the problem before introducing optimization.

Approach 2: Dynamic Programming with Prefix Sum (O(n^2) time, O(n) space)

The standard solution uses dynamic programming. Define dp[i] as the minimum cost to divide the prefix ending at index i. For every position i, iterate backward over possible previous cut points j. The transition becomes dp[i] = min(dp[j] + cost(j+1..i)). To avoid recomputing segment costs repeatedly, precompute cumulative sums using prefix sums. This allows constant‑time cost calculation for any subarray. The DP processes n states and checks up to n previous cuts, giving O(n^2) time and O(n) memory.

Approach 3: DP with Precomputation of Segment Costs (O(n^2) time, O(n^2) space)

Another practical variant precomputes the cost of every subarray cost[i][j] using prefix sums or incremental updates. After building this table, the DP transition becomes a direct lookup when evaluating partitions. This removes repeated arithmetic inside the DP loop and can simplify implementation, though it increases memory usage to O(n^2). It still performs O(n^2) transitions but often runs faster in practice because each state update becomes a constant‑time table lookup.

Recommended for interviews: Interviewers expect the dynamic programming approach with prefix sums. Start by describing the brute force partition idea to show understanding of the search space, then transition to the optimized DP formulation. Using array traversal with prefix sums to compute segment costs in constant time demonstrates strong problem‑solving and optimization skills.