Optimization with dynamic programming is a method for solving complex decision problems by breaking them into smaller overlapping subproblems. Students need this cheat sheet to recognize when a problem can be solved recursively and then organized efficiently. It is especially useful for path planning, scheduling, resource allocation, and shortest path problems.
The main goal is to find the best total value, such as minimum cost or maximum reward, without repeating unnecessary work.
The core idea is to define a state, write a recurrence, choose a base case, and compute the best value for each state. A Bellman equation expresses the optimal value as the best choice among possible next actions. Memoization solves states top down and stores answers, while tabulation fills a table bottom up.
Correct dynamic programming depends on optimal substructure, overlapping subproblems, and a clear order for computing states.
Key Facts
- A dynamic programming state is a set of variables that fully describes the information needed to make the next optimal decision.
- A Bellman recurrence often has the form V(s) = max over actions a of [reward(s, a) + V(next(s, a))] for maximization problems.
- For minimization problems, the recurrence often has the form C(s) = min over actions a of [cost(s, a) + C(next(s, a))].
- A base case gives a known value, such as V(goal) = 0 or C(0) = 0, so the recurrence has a place to stop.
- Memoization uses top-down recursion with storage, so each state is computed once and reused when needed.
- Tabulation uses a bottom-up table, filling smaller or later-known states before larger states that depend on them.
- The time complexity is usually about number of states times number of choices per state, written as O(states x choices).
- An optimal solution can be reconstructed by storing the action that produced the best value at each state.
Vocabulary
- State
- A state is a compact description of the current situation that contains all information needed for future decisions.
- Bellman equation
- A Bellman equation is a recurrence that defines the best value of a state using the best choice among possible actions.
- Optimal substructure
- Optimal substructure means an optimal solution to the whole problem contains optimal solutions to its smaller subproblems.
- Overlapping subproblems
- Overlapping subproblems occur when the same smaller states are needed many times in a recursive solution.
- Memoization
- Memoization is a top-down technique that stores the result of each solved state so it is not recomputed.
- Tabulation
- Tabulation is a bottom-up technique that fills a table of state values in an order that respects the recurrence.
Common Mistakes to Avoid
- Choosing an incomplete state, because leaving out needed information makes two different situations look the same and can produce a wrong optimum.
- Forgetting the base case, because the recurrence will not know where to stop or what value to use at the simplest state.
- Using max when the problem asks for minimum, because the direction of optimization must match the goal such as least cost or greatest reward.
- Filling a table in the wrong order, because a state must be computed only after the states it depends on are already known.
- Counting recursive calls instead of unique states, because dynamic programming efficiency comes from solving each unique state once.
Practice Questions
- 1 A robot can move right or down on a 3 by 3 grid from the top-left corner to the bottom-right corner. If each move has cost 1, write a recurrence for the minimum number of moves from cell (i, j) to the goal.
- 2 For the recurrence C(n) = min(C(n - 1) + 2, C(n - 2) + 5), with C(0) = 0 and C(1) = 2, calculate C(2), C(3), and C(4).
- 3 A knapsack has capacity 5. Items have weights and values: A has weight 2 and value 6, B has weight 3 and value 10, and C has weight 4 and value 12. What is the maximum value if each item can be used at most once?
- 4 Explain why a problem with no overlapping subproblems may not benefit much from dynamic programming, even if it can be solved recursively.
Understanding Optimization with Dynamic Programming
The hardest part is usually choosing the state. A state must include every fact that can change the future decision, but nothing irrelevant. In a backpack packing problem, the state may be the number of items considered and the remaining weight capacity.
The exact order in which earlier items were packed does not matter if it does not affect the remaining capacity. In a route problem, the current location may be enough, or the state may need to include time, fuel, or visited locations. Missing needed information produces answers that look reasonable but are wrong.
A recurrence needs to account for every legal choice from a state. For each choice, calculate its immediate result, then combine it with the best result available afterward. This works because an optimal full plan cannot contain a wasteful continuation.
If it did, replacing that continuation with a better one would improve the full plan. This is the reasoning behind optimal substructure. Students should state this argument clearly when explaining why their recurrence is valid.
They should check whether choices interact across time. A choice that changes future rules, such as using a limited coupon or visiting a location only once, requires that fact to be recorded in the state.
The direction of computation matters. In a grid, a cell may depend only on cells above it and to its left. Filling rows from top to bottom then makes every needed value available.
In a coin problem, a total can depend on smaller totals, so start from zero and move upward. Memoization is often easier to write because the recursive code follows the recurrence closely. Tabulation is often easier to inspect because the table reveals the order of work.
Both methods fail if dependencies form an unresolved cycle. Problems with cycles, such as routes that can revisit places, may need extra restrictions or a different shortest path method.
Real systems use this kind of planning when choosing delivery routes, dividing limited time among tasks, aligning text in search tools, or deciding which files fit into storage. The same logic appears in exam problems involving stairs, sequences, grids, budgets, and schedules. Do not stop after finding the best value.
Many tasks ask for the actual route, chosen items, or schedule. Store the decision that wins at each state, then trace backward from the final state. Test a solution on tiny cases by listing all possibilities manually.
Pay special attention to impossible states, ties between choices, zero capacity, empty inputs, and whether the goal is to minimize or maximize. These details cause many otherwise correct programs to fail.