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.
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
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.
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