Dynamic programming is a problem-solving technique for algorithms that break a big problem into smaller overlapping subproblems. This cheat sheet helps students recognize common DP patterns instead of starting from scratch every time. It is useful for coding interviews, programming contests, and high school computer science courses.
The main goal is to define states clearly, write correct transitions, and choose an efficient evaluation order.
Most dynamic programming solutions use a state, a recurrence, base cases, and an answer location. Memoization solves states with recursion and caching, while tabulation fills a table in a planned order. Common patterns include 1D sequences, grid paths, 0/1 knapsack, longest increasing subsequence, and interval DP.
Time and space complexity usually depend on the number of states multiplied by the work needed for each transition.
Key Facts
- A DP state describes a subproblem, such as dp[i] for the best answer using the first i items or ending at index i.
- A recurrence defines how to compute a state from smaller states, such as dp[i] = max(dp[i - 1], dp[i - 2] + value[i]).
- Base cases stop the recurrence, such as dp[0] = 0 or dp[0][0] = grid[0][0].
- Memoization uses recursion plus a cache, so solve(state) returns the stored answer if the state was already computed.
- Tabulation fills a table from smaller subproblems to larger subproblems, often using loops in increasing index order.
- For grid path counting with only right and down moves, dp[r][c] = dp[r - 1][c] + dp[r][c - 1].
- For 0/1 knapsack, dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weight[i]] + value[i]) when weight[i] <= w.
- The usual DP time complexity is number of states times transitions per state, and the space complexity is the size of the table or cache.
Vocabulary
- State
- A state is a set of variables that uniquely identifies one subproblem in a dynamic programming solution.
- Recurrence
- A recurrence is a formula or rule that computes a DP state from smaller or earlier states.
- Base Case
- A base case is a smallest subproblem with a known answer that starts the DP computation.
- Memoization
- Memoization is a top-down DP method that stores the result of each recursive subproblem after solving it once.
- Tabulation
- Tabulation is a bottom-up DP method that fills a table in an order that guarantees needed values are already known.
- Transition
- A transition is one possible move or choice used to update a DP state from another state.
Common Mistakes to Avoid
- Choosing a vague state is wrong because the recurrence may not have enough information to compute the answer correctly. Define exactly what each index or variable means.
- Forgetting base cases is wrong because recursion may never stop or a table may use undefined values. Always write the smallest valid subproblems before coding transitions.
- Using the wrong loop order in tabulation is wrong because a state might read a value that has not been computed yet. Fill the table so every dependency comes earlier.
- Mixing up 0/1 knapsack and unbounded knapsack is wrong because 0/1 items can be used once, while unbounded items can be reused. The recurrence and loop direction must match the item rule.
- Reporting only the recurrence without complexity is incomplete because DP is judged by both correctness and efficiency. Count the number of states and multiply by the transitions per state.
Practice Questions
- 1 For the recurrence dp[i] = dp[i - 1] + dp[i - 2] with dp[0] = 0 and dp[1] = 1, compute dp[6].
- 2 A grid has 3 rows and 4 columns, and you may move only right or down from the top-left to the bottom-right. How many unique paths are there?
- 3 For items with weights [2, 3, 4], values [4, 5, 7], and capacity 5, what is the maximum value using 0/1 knapsack?
- 4 Explain why a problem with repeated subproblems and optimal substructure is a good candidate for dynamic programming.
Understanding Dynamic Programming Patterns
The hardest part of dynamic programming is usually choosing the information that belongs in a state. A good state keeps every detail that can change future choices, but throws away details that no longer matter. For a backpack problem, the important facts may be how many objects have been considered and how much capacity remains.
The exact order in which earlier objects were chosen may not matter. This idea is called sufficient information. Students often make states too small and lose needed facts, or too large and create far too many cases.
Pay close attention to words such as exactly, at most, ending at, starting at, and remaining. Each phrase can change what the state must mean.
Every transition should represent a real choice or a real last step. For example, when finding the cheapest way to reach a location, imagine the final move into that location. The answer must come from one of the places that could lead there.
This viewpoint makes many recurrences easier to build. It is useful to draw arrows from each smaller state to the states that depend on it. The arrows must point in one direction.
If a state depends on itself before becoming smaller, the plan has a cycle and needs to be redesigned. Memoization follows only states that are actually reached, which can save work in sparse problems.
Tabulation can be easier to inspect because each table entry is filled in a visible order. Recursive solutions can fail on very deep inputs because of call stack limits.
Different patterns mainly differ in what counts as a previous state. In a sequence problem, earlier positions are candidates. In a grid, nearby cells are candidates, though blocked cells must contribute nothing.
In a selection problem, each object creates a take choice and a skip choice. A common mistake in zero or one selection problems is updating a one-dimensional capacity array from low capacity to high capacity. That can accidentally use the same object more than once.
Updating from high capacity down to low capacity prevents this. For longest increasing subsequence, the previous value matters because only smaller values can precede the current one.
For interval problems, solve short ranges before long ranges. A range may be split at every possible middle position, so these problems often need more time than simple sequence problems.
Dynamic programming appears in route planning, text comparison, spell checking, budgeting, game scoring, and scheduling. The real-world story may look different, yet the core task is often to reuse answers for repeated situations. Test a solution with the smallest possible input before trusting it.
Include empty inputs, one item, zero capacity, blocked starts, repeated values, and impossible cases. Write down what each table entry means in a full sentence. Then check that the base cases match that sentence and that every transition preserves it.
If the task requires the actual chosen path or objects, store a parent choice while computing values, then trace backward from the final answer. This reconstruction step is separate from finding the best score, and forgetting it is a frequent contest mistake.