What is Dynamic Programming?
Dynamic Programming, or DP, solves a problem by remembering answers to smaller versions of the same problem. It is useful when different paths of choices reach the same smaller state.
You need recursion, arrays or maps, and basic complexity analysis. The short version is: define a state once, solve it once, and reuse its answer everywhere.
The Core Idea: Reuse Smaller Answers
In LC 509: Fibonacci (n=8), F(8) needs F(7) and F(6).
A direct recursive call for F(7) also computes F(6) again.
How do we stop repeating that work?
We store each Fibonacci value the first time it is known.
Then F(8) reads two stored values and produces 21.
It is like keeping completed answers on a worksheet. When a later question uses an earlier result, you read the answer instead of solving that question again.
From Repeated Calls to a Table
The Rule You Keep True
Every stored DP entry must equal the answer for the state named by its index or key. Before calculating a state, every state used by its recurrence must already be correct.
The shape depends on the state:
- One-dimensional sequence DP uses earlier indexes, as in Fibonacci and Climbing Stairs.
- Take-or-skip DP compares choosing the current item with leaving it, as in House Robber.
- Amount DP tries each choice that can reach a remaining total, as in Coin Change.
- Sequence DP records the best answer ending at or comparing chosen positions.
Coin Change is the one that usually trips us up. The table entry means the fewest coins for one exact amount, and unreachable amounts must stay impossible rather than quietly behaving like zero.
Picking the Right Shape
From Rule to Code
- Define the state in one sentence, including every value needed to identify a subproblem.
- Write the base states whose answers are already known.
- Write the recurrence by listing the choices from one state.
- Compute states with memoized recursion or in an order that satisfies dependencies.
- Return the state representing the original problem.
The algorithm finishes because each finite state is computed at most once. Time is usually the number of states multiplied by the work needed to process one state.
When to use it
- •A problem asks for an optimum, count, or yes-or-no result over many related choices.
- •A direct recursive solution solves the same smaller input more than once.
- •The answer for one state can be built from answers to smaller states.
- •The prompt contains repeated decisions such as take or skip, choose a coin, or extend a sequence.
How to identify it
- •You can describe a state using a small set of values such as an index, remaining amount, or previous choice.
- •Different decision paths can arrive at the same state.
- •The problem asks for minimum, maximum, number of ways, or whether a result is possible.
- •A recurrence can express the current answer using already solved states.
Key insights
- →The state definition is the meaning of one table entry and must be written before the recurrence.
- →A recurrence lists the choices available from one state and combines their results.
- →Memoization caches recursive states, while tabulation fills them in dependency order.
- →Base cases are real solved states, not special patches added after the recurrence.
- →Space can be reduced only when future states need a limited part of the table.
Common mistakes
- 01Writing a recurrence before defining what `dp[i]` means.
- 02Caching too little state so different subproblems share the same key.
- 03Filling a table before the states it depends on are ready.
- 04Using a greedy choice where later decisions can change which earlier choice was best.
- 05Optimizing space before the full recurrence is correct.