# Dynamic programming example

### From HaskellWiki

(Difference between revisions)

(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 arrayr

r!0

True

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)