What is dynamic programming?
Dynamic programming is a technique for solving a problem by breaking it into smaller overlapping subproblems and storing each answer so you never solve the same subproblem twice. It suits problems with overlapping subproblems and an optimal substructure, where the best answer is built from the best answers to smaller parts. It turns slow exponential solutions into fast ones.
- Dynamic programming breaks a problem into overlapping subproblems and stores each answer to avoid recomputing it.
- It suits problems with overlapping subproblems and optimal substructure, like Fibonacci or shortest paths.
- Memoisation caches results top down, while tabulation fills a table bottom up.
The key signal
If a plain recursive solution keeps recomputing the same values, dynamic programming helps. The classic example is Fibonacci, where naive recursion recomputes the same numbers many times.
// Top down with memoisation
unordered_map<int, long> memo;
long fib(int n) {
if (n <= 1)
return n;
if (memo.count(n))
return memo[n];
return memo[n] = fib(n - 1) + fib(n - 2);
}// Top down with memoisation
Map<Integer, Long> memo = new HashMap<>();
long fib(int n) {
if (n <= 1)
return n;
if (memo.containsKey(n))
return memo.get(n);
long r = fib(n - 1) + fib(n - 2);
memo.put(n, r);
return r;
}# Top down with memoisation
def fib(n, memo={}):
if n <= 1:
return n
if n in memo:
return memo[n]
memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
return memo[n]Two common styles
- Top down: normal recursion plus a cache, called memoisation.
- Bottom up: fill a table from the smallest subproblems upward, called tabulation.
When you spot repeated subproblems in your recursion, say the word memoisation and explain you will cache results. That single move often takes a solution from O(2 to the n) down to O(n), which is exactly what interviewers want to hear.
Frequently asked questions
What is the difference between memoisation and tabulation?
Memoisation is top down recursion with a cache, while tabulation is bottom up iteration filling a table. Both store subproblem answers to save work.
How is dynamic programming different from divide and conquer?
Divide and conquer splits into independent subproblems, while dynamic programming reuses overlapping subproblems whose answers repeat.
Common follow up questions
Related interview questions
Want the full DSA guide?
Read every DSA concept with notes, diagrams, and code in one place. Track your progress as you go.
Open the DSA guide All DSA questions