Back to Topics
Dynamic Programming
Dynamic programming (DP) solves complex problems by breaking them into overlapping sub-problems and storing their results to avoid redundant computation. It applies when a problem has optimal substructure (the optimal solution contains optimal solutions to sub-problems) and overlapping sub-problems (the same sub-problem is solved more than once).
Key Ideas
- Top-down (memoisation): recursive solution + cache to skip repeated sub-problems
- Bottom-up (tabulation): fill a DP table iteratively from base cases
- State definition is the hardest part: dp[i] must encode everything needed to answer sub-problems
- Transition equation defines how dp[i] is computed from previous states
- 1D DP for sequence problems; 2D DP for two-sequence problems (e.g. LCS, edit distance)
- Space optimisation: many 2D DPs can be reduced to O(n) by keeping only the previous row
Complexity
| Operation | Time | Space |
|---|---|---|
| 1D DP (Fibonacci, coin change) | O(n) | O(n) or O(1) |
| 2D DP (LCS, edit distance) | O(n·m) | O(n·m) or O(m) |
| Knapsack (0/1) | O(n·W) | O(n·W) or O(W) |
| Matrix chain multiplication | O(n³) | O(n²) |
Common Patterns
Linear DP (1D)dp[i] depends on previous few states — classic for Fibonacci, house robber, climbing stairs.
KnapsackInclude or exclude each item; dp[i][w] = max value using first i items with capacity w.
Two-sequence DPdp[i][j] = answer for prefix s1[:i] and s2[:j] — used for LCS, edit distance.
Interval DPdp[i][j] = answer over subarray [i, j]; fill by increasing length of interval.
Code Example
Longest Common Subsequence — 2D DPpython
def lcs(text1: str, text2: str) -> int:
m, n = len(text1), len(text2)
# dp[i][j] = LCS length of text1[:i] and text2[:j]
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]💡
If you need all combinations (backtracking) but sub-problems repeat → DP. Start by writing the recursive solution, then add memoisation.