Implementing dynamic programs in spreadsheets

This paper has two purposes: to help explain dynamic programs (DP) to students who have no background in procedural languages, and to quantitatively motivate good spreadsheet designs that can be developed and modified easily. Teachers and practitioners could benefit from using spreadsheets to solve the common problems that are suited to DP. We give examples of several imortant DPs, implemented in different ways with a spreadsheet. We further analyze these DPs for their constructive complexity, which is the number of keystrokes required to write a spreadsheet for a given computational task, as a function of the input data. We show that a given DP can be written in several ways, with varying constructive complexity. The implementation can drastically affect the difficulty of writing and modifying a spreadsheet. The different examples demonstrate the value of good spreadsheet design.