dynamic programming and the use of matrices

Question

I'm always confused about how dynamic programming uses the matrix to solve a problem. I understand roughly that the matrix is used to store the results from previous subproblems, so that it can be used in later computation of a bigger problem.

But, how does one determine the dimension of the matrix, and how do we know what value each row/column of the matrix should represent? ie, is there like a generic procedure of constructing the matrix?

For example, if we're interested in making changes for S amount of money using coins of value c1,c2,....cn, what should be the dimension of the matrix, and what should each column/row represent?

Any directional guidance will help. Thank you!

Answer 1

A problem becomes eligible for dynamic programming when it exhibits both Overlapping Sub-problems as well as Optimal Substructure.

Secondly, dynamic programming comes in two variations:

• Tabulation or the Bottom-up approach
• Memoization or the Top-down approach (not MemoRization!)

Dynamic Programming stems from the ideology that a large problem can be further broken down into sub-problems. The bottom-up version simply starts with solving these sub-problems first and gradually building up the target solution. The top-down approach relies on using auxiliary storage doing away with re-computation.

is there like a generic procedure of constructing the matrix?

It really depends on what problem you're solving and how you're solving it! Matrices are typically used in tabulation, but it always need not be a matrix. The main goal here is to have the solutions to the sub-problems readily available on demand, it could be stored in an array, a matrix or even a hash-table.

The classic book Introduction to Algorithms demonstrates the solution to the rod-cutting problem in both ways where a 1D array is used as auxiliary storage.

For example, if we're interested in making changes for S amount of money using coins of value c1,c2,....cn, what should be the dimension of the matrix and what should each column/row represent?

If I'm not wrong, you're referring to the "total unique ways to make change" variant of the coin-change problem. You need to find the total ways a given amount can be constructed using given set of coins. There is a great video on this that breaks it down pretty well. It uses a bottom-up approach: https://www.youtube.com/watch?v=DJ4a7cmjZY0

Assume you need to construct amount n = 10 from the given subset of coins c = {1, 2, 10} Take an empty set and keep adding the coins one per row from c. For every next row, one coin from the set is added. The columns represent the sub-problems. For i in n = 1 : 10, the ith column represents the the total number of ways i can be constructed using the coins in that row:

--------------------------------------------------------            |0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | -------------------------------------------------------- |{}        |  |   |   |   |   |   |   |   |   |   |    | -------------------------------------------------------- |{1}       |  | X |   |   |   |   |   |   |   |   |    | -------------------------------------------------------- |{1, 2}    |  |   |   |   |   |   |   |   |   |   |    | -------------------------------------------------------- |{1, 2, 10}|  |   |   | Y |   |   |   |   |   |   | Z  | -------------------------------------------------------- 

In this table, X represents the number of ways amount 1 can be constructed using the coin {1}, Y represents the number of ways amount 3 can be represented using the coins {1, 2, 10} and Z represents the number of ways amount 10 can be represented using the coins {1, 2, 10}.

How are the cells populated?

Initially, the entire first column headed by 0 is filled with 1s because no matter how many coins you have, for the amount 0 you have exactly one way to make change that is to make no change. The rest of the first row with the empty subset {} is filled with 0s because you can't make a change for any positive amount with no coins. Now the matrix looks like this:

--------------------------------------------------------             0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | -------------------------------------------------------- |{}        |1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |  0 | -------------------------------------------------------- |{1}       |1 | X |   |   |   |   |   |   |   |   |    | -------------------------------------------------------- |{1, 2}    |1 |   |   |   |   |   |   |   |   |   |    | -------------------------------------------------------- |{1, 2, 10}|1 |   |   | Y |   |   |   |   |   |   | Z  | -------------------------------------------------------- 

Now, how do we fill X? You have two alternatives, either to use the 1 coin in this new super set or to not use it. If you did not use the coin, the ways are same as the above row that is 0. But since 1 can be used to make a change of amount 1, we use that coin, and subtract 1 from the amount 1 to be left with 0. Now lookup, 0's ways in the same row, that is the column previous to that of X which is 1. So add it to the amount from the top row to have a total of 1. So you fill this cell as 1.