Understanding the top down solution to the matrix chain multiplication problem

To solve the matrix chain multiplication problem using a top-down dynamic programming approach, we translate the recurrence relation into a recursive function and use a memoization table to store results of subproblems that have already been solved.

The top down solution

As with any top-down solution, there is a recursive function that solves subproblems and a calling function that initializes the required data structures and triggers the computation. The recurrence relation for the matrix chain multiplication problem relies on a single recursive function, so we define one recursive function along with a calling function that sets up the computation.

The minCost function

The function minCost() takes as input a left index i, a right index j, a reference to the dimensions array dim, and a reference to the 2D memoization array memo. The function returns the minimum number of scalar multiplications needed to compute the product of the matrices from index i to index j in the chain.

Create a function minCost to return the minimum cost of multiplying the subchain of matrices from index i to j.

The memo array has dimensions (n + 1) × (n + 1) and is initialized with -1 in the calling function, where -1 indicates that the state has not yet been computed. Any non-negative value represents the computed minimum multiplication cost for that subchain.

Why does the memo array have size (n + 1) × (n + 1) instead of n × n?

The matrices in the chain are indexed from 1 to n, matching the problem statement, where the matrix at index m has dimensions dim[m - 1] × dim[m]. To use these positions directly as indices into memo without any offset arithmetic, we allocate memo with dimensions (n + 1) × (n + 1) and leave row 0 and column 0 unused. This costs us a tiny strip of unused memory but keeps the indexing in the code consistent with the indexing in the recurrence.