Algorithms (CS 301) Dynamic Programming Patterns Cheat Sheet: Knapsack, LIS, Coin Change, DAG DP
Georgia Institute of Technology
Algorithms (CS 301) | Study Guide

Overview
A finals-week dynamic programming cheat sheet for CS 301: spotting DP, defining state and transitions, and avoiding the most common table and indexing mistakes.

Key topics
•when DP is the right tool (overlapping subproblems, optimal substructure)
•state design for 1D vs 2D DP
•common patterns (0/1 knapsack, unbounded, LIS, coin change)
•top-down vs bottom-up and complexity
•reconstruction and edge cases

Suggested study tasks
•turn 8 prompts into state/transition definitions
•fill 4 DP tables by hand (with indexing notes)
•rewrite 3 recursive solutions into iterative bottom-up
•do 6 small counterexamples to check base cases
•practice reconstructing choices for knapsack and LIS

Common pitfalls
•using DP without proving optimal substructure
•off-by-one indexing in tables
•forgetting base cases leading to impossible states
•mixing 0/1 and unbounded transitions
•not tracking choices so you cannot reconstruct the solution