Dynamic programming example
(Creation and first example)
Revision as of 04:06, 11 April 2007
Dynamic programming refers to translating a problem to be solved into a recurrence formula, and crunching this formula with the help of an array (or any suitable collection) to save useful intermediates and avoid redundant work.
Computationally, dynamic programming boils down to write once, share and read many times. This is exactly what lazy functional programming is for.
1 Sample problems and solutions
1.1 Available in 6-packs, 9-packs, 20-packs
A fast food place sells a finger food in only boxes of 6 pieces, boxes of 9 pieces, or boxes of 20 pieces. You can only buy zero or more such boxes. Therefore it is impossible to buy exactly 5 pieces, or exactly 7 pieces, etc. Can you buy exactly N pieces?If I can buy i-6 pieces, or i-9 pieces, or i-20 pieces (provided these are not negative numbers), I can then buy i pieces (by adding a box of 6 or 9 or 20). Below, I set up the array
import Data.Array buyable n = r!n where r = listArray (0,n) (True : map f [1..n]) f i = i >= 6 && r!(i-6) || i >= 9 && r!(i-9) || i >= 20 && r!(i-20)