Dynamic Programming Basics
DSA · Dynamic Programming
Theory
Dynamic programming (DP) solves problems that have overlapping sub-problems and optimal substructure by solving each sub-problem once and storing its answer. Top-down DP (memoisation) adds a cache to a recursive solution; bottom-up DP (tabulation) fills a table from the smallest sub-problems upwards. The steps are: define the state, write the recurrence, set base cases, and choose the computation order.
Why we use it
DP turns exponential brute-force solutions into polynomial ones, often O(n) or O(n²).
When to use it
Use DP when a problem asks for a count, minimum, maximum or yes/no answer that can be built from answers to smaller versions, and the same smaller versions repeat.
How it works
- Define state dp[i]
- Write recurrence from smaller states
- Set base cases
- Top-down? Yes: Recursion + memo. No: Bottom-up: fill table in order.
- Answer = dp[target]
Syntax
Top-down: memo = {}; def f(n): if n in memo: return memo[n]; ...
Bottom-up: dp = [base]; for i in range(...): dp[i] = recurrence
1. State 2. Recurrence 3. Base cases 4. OrderExample
calls = [0]
def fib_plain(n):
calls[0] += 1
return n if n < 2 else fib_plain(n - 1) + fib_plain(n - 2)
memo = {}
def fib_memo(n):
if n in memo:
return memo[n]
memo[n] = n if n < 2 else fib_memo(n - 1) + fib_memo(n - 2)
return memo[n]
def fib_table(n):
dp = [0, 1]
for i in range(2, n + 1):
dp.append(dp[i - 1] + dp[i - 2])
return dp[n]
print("Plain fib(20):", fib_plain(20), "with", calls[0], "calls")
print("Memoised fib(80):", fib_memo(80))
print("Tabulated fib(80):", fib_table(80))Key points
- Overlapping sub-problems + optimal substructure
- Memoisation = top-down with a cache
- Tabulation = bottom-up table
- Define state, recurrence and base cases