When to use DPCore idea
A problem is a DP candidate when it has both of these:
Optimal substructure
The best answer can be built from the best answers to smaller subproblems.
Overlapping subproblems
A plain recursive solution solves the same subproblems again and again.
If your recursive solution is exponential and keeps calling the same inputs, DP can usually bring it down to polynomial time.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","actorBkg":"#e7f5ff","actorBorder":"#1e1e1e","noteBkgColor":"#fff9db","noteBorderColor":"#1e1e1e"}}}%%
graph TD
F5["fib(5)"] --> F4["fib(4)"]
F5 --> F3["fib(3)"]
F4 --> F3B["fib(3)"]
F4 --> F2["fib(2)"]
F3B --> F2B["fib(2)"]
F3B --> F1B["fib(1)"]
F3 --> F2C["fib(2)"]
F3 --> F1C["fib(1)"]
class F5,F4 blue
class F3,F2,F1B,F1C yellow
class F3B,F2B,F2C red
classDef orange fill:#ffd8a8,stroke:#1e1e1e,color:#1e1e1e
classDef blue fill:#a5d8ff,stroke:#1e1e1e,color:#1e1e1e
classDef green fill:#b2f2bb,stroke:#1e1e1e,color:#1e1e1e
classDef red fill:#ffc9c9,stroke:#1e1e1e,color:#1e1e1e
classDef violet fill:#d0bfff,stroke:#1e1e1e,color:#1e1e1e
classDef yellow fill:#ffec99,stroke:#1e1e1e,color:#1e1e1e
classDef grey fill:#e9ecef,stroke:#1e1e1e,color:#1e1e1eMemoization vs tabulationCompare
Memoizationtop-down
Write the recursive solution, then add a cache. Start from the full problem and work down.
Tabulationbottom-up
Fill a table from the smallest subproblem up. No recursion, so no stack overflow risk.
function fib(n: number, memo: Map<number, number> = new Map()): number {
if (n <= 1) return n;
if (memo.has(n)) return memo.get(n)!;
const result = fib(n - 1, memo) + fib(n - 2, memo);
memo.set(n, result);
return result;
}function fib(n: number): number {
if (n <= 1) return n;
const dp = new Array(n + 1).fill(0);
dp[0] = 0; dp[1] = 1;
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}Common DP patternsPattern
| Pattern | The question | State |
|---|---|---|
| Knapsack | Pick items with weights and values to get the most value under a weight limit. | (item index, remaining capacity) |
| Longest common subsequence | Find the longest sequence that appears, in order, in both strings. | (index in string 1, index in string 2) |
| Coin change | Find the fewest coins that make a target amount. | (remaining amount) |
| Climbing stairs / house robber | At each step, take it or skip it. | (current position): 1D DP |
Steps to solve any DP problemHow it works
Define the state
Which values uniquely describe one subproblem? For example, dp[i] = the answer for the first i items.
Write the recurrence
How does dp[i] come from smaller states? This is the heart of the solution.
Set the base cases
Which subproblems are small enough to answer directly?
Choose the order
Which states must be computed first, so every value you need already exists?
Read off the answer
Which cell of the table holds the final answer?
Common mistakesPitfalls
In the interviewIn the interview
Brute force → notice repeats → memoize → count states × work per state. Interviewers like seeing that path.
Frequently asked questionsFAQ
How do you know if a problem can be solved with dynamic programming?
Look for overlapping subproblems and optimal substructure: the same subproblem recurs, and the optimal answer is assembled from optimal answers of smaller instances. Classic signals are choose-or-skip decisions, and subsequence problems where a naive recursion recomputes identical states over and over.
When should you use memoization versus tabulation?
Memoization, or top-down, follows the recursion directly, computes only needed states, and is easier to write, but adds recursion depth risk. Tabulation, or bottom-up, avoids recursion and enables space optimizations like rolling arrays. Prefer bottom-up when depth or memory matters.
How do you optimize the space used by a DP solution?
Many DP problems depend only on the previous one or two states, so a full table can be replaced with rolling variables, shrinking space from O(n) or O(n^2) to O(1). Preserve the recurrence order carefully, because overwriting states in the wrong direction, as in knapsack, changes the answer.
Now explain dynamic programming to me out loud
I'll give you interview problems and ask follow-ups, like a real interviewer.