Understanding the bottom up solution to the matrix chain multiplication problem

To solve the matrix chain multiplication problem using a bottom-up dynamic programming approach, we fill a table iteratively beginning from the smallest subproblems and building towards the final answer. As with any bottom-up solution, we process subproblems in an order that guarantees every result we depend on has already been computed and stored before we need it.

The bottom up solution

We solve this problem by building a single 2D table that records, for every pair of matrix positions (i, j), the minimum cost of multiplying the subchain of matrices from index i to index j. We fill this table starting from the smallest subchains (single matrices, which need no multiplication) and progressively combine them to compute results for longer subchains.

To determine the minimum cost for each subchain, we create a 2D integer array minCost of dimensions (n + 1) × (n + 1), where minCost[i][j] stores the minimum number of scalar multiplications needed to multiply the subchain from index i to index j. The matrices in the chain are indexed from 1 to n, where the matrix at index m has dimensions dim[m - 1] × dim[m], so the array dim has length n + 1.

We initialize all entries of minCost to infinity, representing "no valid cost found yet". For languages that do not have a native infinity value for integers (such as C++ or Java), we use the largest representable integer value as the sentinel instead.