208. Matrix Chain Multiplication - Minimum Cost

Given n matrices to multiply together in a fixed order, described by n+1 dimensions (matrix i has size dims[i-1] x dims[i]), find the minimum total number of scalar multiplications needed, choosing the best order to parenthesize the multiplications.

Input: The first line contains an integer n, the number of matrices. The second line contains n+1 space-separated integers representing the dimensions array, where matrix i has size dims[i-1] x dims[i]. Output: Print a single integer - the minimum total number of scalar multiplications needed.

1 <= n <= 500

This is the canonical INTERVAL DP problem - the same 'try every split point, combine two independent sub-ranges' technique reappears throughout this category (Optimal BST, Boolean Parenthesization, Palindrome Partitioning) with different cost/count formulas plugged into the same overall structure.

Find the minimum total scalar multiplications needed to multiply a chain of matrices, choosing the best parenthesization. Brute force: Try every possible way of fully parenthesizing the matrix chain directly and compute each one's total cost - the number of possible parenthesizations grows combinatorially (the (n-1)th Catalan number), impractical for larger n without memoization. Optimised: The interval DP recognizes that once a SPLIT POINT is chosen for a chain, the LEFT and RIGHT sub-chains become INDEPENDENT optimal sub-problems - trying every possible split and reusing already-computed shorter sub-chain costs avoids re-deriving the same sub-chain's optimal cost repeatedly.

Recursively try every possible place to split the chain of matrices into a left part and a right part, recursively find the minimum cost of each part, and add the cost of multiplying the two resulting matrices together, taking the best split over all choices. This directly enumerates every possible parenthesization (there are Catalan(n-1) of them), so it's correct but re-solves the exact same sub-chains over and over, making it exponential. Time: O(2^n) (exponential, Catalan growth) Space: O(n)

Fill a 2D DP table iteratively by increasing chain length: first solve all sub-chains of length 2, then length 3, and so on, so that whenever a sub-chain's cost is needed for a split, it has already been computed. This produces the identical answer as the memoized recursion but does it iteratively with no function-call/recursion-stack overhead, which matters here since n can be up to 500 and a deep recursive memoization could risk stack depth issues; the bottom-up table is also easy to reason about and traceable for reconstructing the optimal parenthesization if needed. Time: O(n^3) Space: O(n^2)

Keep the exact same recursive split logic as the brute-force approach, but cache the minimum cost for every (i, j) sub-chain the first time it's computed in a 2D memo table, and return the cached value immediately on repeat calls. Since there are only O(n^2) distinct sub-chains and each is solved once by trying O(n) split points, this collapses the exponential blowup into polynomial time while keeping the same recursive structure. Time: O(n^3) Space: O(n^2)

1. dp[i][j] = minimum cost to multiply the chain of matrices from i to j. 2. Try every SPLIT POINT k between i and j: dp[i][j] = min over k of dp[i][k] + dp[k+1][j] + dims[i-1]*dims[k]*dims[j]. 3. Build the table by increasing chain length, since dp[i][j] depends on strictly shorter sub-chains.

Time: O(n³) - for each of the O(n²) sub-chains, trying every possible split point costs O(n). Space: O(n²), for the dp table.

Test n = 1 (a single matrix, requiring zero multiplications) and n near the upper bound of 500 to confirm the O(n^3) DP runs in time; dimension values can vary widely in magnitude.

Be ready to explain the cost FORMULA precisely (dims[i-1]*dims[k]*dims[j] represents the cost of the FINAL multiplication combining the two resulting sub-products, given their respective dimensions) - this specific formula, not just 'try every split', is the crux of correctly computing each candidate cost.