Algorithm
Dynamic programming stores the answers to overlapping subproblems and reuses them, turning exponential searches into efficient table-filling algorithms.
Dynamic programming (DP) is an algorithm design technique that splits a problem into smaller subproblems, solves each subproblem once, stores the answer and reuses it whenever the same subproblem appears again. Formalized by Richard Bellman in the 1950s, it applies when subproblems overlap and when an optimal solution can be assembled from optimal solutions to its subproblems.
DP turns many problems that take exponential time with plain recursion or brute force into ones that run in time proportional to the number of states. It powers diff tools, edit distance in spell checkers, DNA sequence alignment, Viterbi decoding in speech recognition and join ordering in database query planners, and it is one of the most frequent topics in coding interviews.
Start with Fibonacci to see the difference between memoization (top-down) and tabulation (bottom-up), then work through the classics: coin change, 0/1 knapsack, longest increasing subsequence, longest common subsequence and edit distance. For every problem, write down the state, recurrence, base cases and evaluation order first, fill a small table by hand to check the recurrence, and only then write code.
When the same subproblem appears many times, DP computes it once and stores the result, turning repeated work into a table lookup.
An optimal solution must be buildable from optimal solutions to subproblems; this property is what justifies the recurrence.
Implement DP top-down by adding a cache to recursion (functools.cache) or bottom-up by filling a table with loops.
Choose the smallest set of parameters that determines the answer, and keep only the rows you need with rolling arrays.
knapsack solves the 0/1 knapsack problem bottom-up with a single row, iterating capacities from high to low so each item is used at most once. lcs computes the length of the longest common subsequence top-down, memoized with functools.cache. Running python dynamic_programming.py prints 9 and 4.
dynamic_programming.py
from functools import cache
def knapsack(weights, values, capacity):
"""0/1 knapsack: best total value within capacity (bottom-up, one row)."""
best = [0] * (capacity + 1)
for w, v in zip(weights, values):
for c in range(capacity, w - 1, -1): # high to low: each item used at most once
best[c] = max(best[c], best[c - w] + v)
return best[capacity]
def lcs(a, b):
"""Length of the longest common subsequence (top-down, memoized)."""
@cache
def solve(i, j):
if i == len(a) or j == len(b):
return 0
if a[i] == b[j]:
return 1 + solve(i + 1, j + 1)
return max(solve(i + 1, j), solve(i, j + 1))
return solve(0, 0)
print(knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7)) # 9
print(lcs("ABCBDAB", "BDCABA")) # 4
python dynamic_programming.pySix chapters that take you from installation to the core ideas of Dynamic programming.
Ask questions, share experience and trade opinions about Dynamic programming.
No discussions yet. Start the first one.
0 comments
Sign in · Sign in to leave a comment.