Dynamic Programming II: from List to Table
In the previous note, we use cases on factorial and Fibonacci number to illustrate how dp revisit the pre-solved sub-problem as it builds up the solution. They are relatively simple and straight-forward as the solution is dependent on a single variable, or to put it in another way, the solution can be located by one index.
DP problems with more than one index become more obscure. For example, if it needs 2 indices, we are building a table not a list anymore.
Of course, one index is still and always will be n which is directly related to the solution.
The tricky part is the other index, m. The way we define M is the highly correlated to the way we decompose the problem into sub-problems. Although there is no off the shelf conclusion regarding to the definition of M, practice makes perfect: after struggling with several dp problems with 2 indices, you will pick up some heuristic cues.
CASE STUDY: Coin Change
The solution is contingent on n and m. N is just the amount of change you request. M here is the number of types of coins. For example, if there are four types of coins, 1, 2, 3, and 5. If we need 5 cents of change in total, and insist only one type of coin, we may get 1 1 1 1 1 or 5. But M will be 1 in this case.
Of course, the solution to get 10 cents from these 4 types of coins can be TABLE[10][4].
Why do we define M in that way? Because, with that M, we could decompose the problem into sub-problems as,
TABLE[N][M] = TABLE[N-M[i]][M]+TABLE[N][M-1]
TABLE[N-M[i]][M]: All solutions that contain coin type i.
TABLE[N][M-1]: All solutions that do not contain coin type i.
Now that we have that golden equation, we simply specify the initial case and then build up the table.
Reference: