Dynamic programming example

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.

Sample problems and solutions

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 r for exactly that, with r!0 forced to True to bootstrap the whole thing.

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)