Algorithms (CS 301) Dynamic Programming Templates: Knapsack, LIS, and Interval DP Exam Review
School: Georgia Institute of Technology
Course: Algorithms (CS 301)
Document type: Exam Review

Overview
A high-yield DP review that turns common exam problems into reusable templates: define the state, write the transition, pick the iteration order, and check base cases. This note helps students review the DP recipe (state transition base order), 0/1 knapsack and subset-sum patterns, longest increasing subsequence (LIS) DP formulation with clear examples and study prompts.

What this document covers
- the DP recipe (state transition base order)
- 0/1 knapsack and subset-sum patterns
- longest increasing subsequence (LIS) DP formulation
- interval DP (matrix chain style) structure
- memoization vs tabulation and when each is safer

How to use it
1. write state and transition for 6 prompts before touching code
2. fill a small knapsack DP table by hand to verify transitions
3. compute LIS length for 3 arrays using the DP definition
4. solve one interval DP mini example with 5 items and show the split choices
5. debug a broken DP by checking base cases and loop order

Common mistakes to avoid
- choosing a state that cannot answer the question
- using the wrong loop order so dependencies are not computed
- double-counting items in 0/1 problems by iterating forward incorrectly
- missing base cases leading to off-by-one errors
- trying greedy when the problem needs DP proof