4020 Homework Guide
Writing Up Dynamic Programming Solutions
Dynamic programming solutions should typically contain the following.
- Subproblems: Describe what subproblems you are using. For example, if you call a subproblem OPT(j), what does OPT(j) mean?
- Recurrence: State the recurrence, and justify its correctness.
- Full Algorithm: Using short pseudocode or an English description, state the full algorithm that you are using. Specifically, from this the following should be clear: (1) What base cases are being used, (2) The order of filling in the table/array, (3) How to obtain the final solution to the problem. The latter will usually just be a particular entry in the table, but not always.
- Running Time: An analysis of the running time of your algorithm.