Mark As Completed Discussion

Filling the Matrix

Filling the Matrix

The figure shows how the pseudo-code works. Initially the matrix M is empty. Then, for each cell, if a coin denomination (column index j) is an integer multiple of the coin for that row, then fill up that cell with j / coin[i].

Next, fill the matrix row by row as shown in the figure. As an example, for i=2, j=11, the value of the matrix is:

SNIPPET
1M[2][11] = min(M[1][11],M[1][6]+1,M[1][1]+2) = min(4,2+1, inf+2) = 3