Dynamic programming and matrix usage

Question

I am always confused about how dynamic programming uses a matrix to solve a problem. I understand that the matrix is ​​used to store the results from previous subtasks, so it can be used to calculate a larger problem later.

But how to determine the dimension of the matrix and how to find out what value each row / column of the matrix should represent? those. exists as a general matrix construction procedure?

For example, if we are interested in making changes for the amount of money S using coins of values ​​c1, c2, ... cn, what should be the size of the matrix and what should be each column / row?

Any directional guidance will help. Thanks!

Answer 1

Rough steps for some types of DP problems:

• Find a recursive solution

• If some intermediate results of recursive calls are calculated again and again - remember them and use - create a table with the appropriate sizes - this is memoization

• This table can usually be filled from the starting cell to the final (result) - cells by cell, by row, etc ...

For change issue:

• F (s) = F (s-c1) + F (s-c2) + ...

Try to develop a complete recursive solution and determine which table is needed to store the intermediate results.

Answer 2

This chapter explains it very well: http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf On page 178 some approaches to the definition of subprocesses that allow the use of dynamic programming are given.

Answer 3

The array used by the DP solution is almost always based on the size of the state space of the problem, that is, the allowable values ​​for each of its parameters

for instance

fib[i+2] = fib[i+1] + fib[i] 

Same as

 def fib(i): return fib(i-1)+fib(i-2] 

You can make this more obvious by doing memoization in your recursive functions

 def fib(i): if( memo[i] == null ) memo[i] = fib(i-1)+fib(i-2) return memo[i] 

If your recursive function has parameters K, you probably need a K-dimensional matrix.