Dynamic Programming — How the Pattern Works
Dynamic Programming solves optimization, counting, and decision problems that exhibit optimal substructure and overlapping subproblems by decomposing them into smaller self-similar states and computing each distinct state exactly once. Whether implemented via bottom-up tabulation or top-down memoization, it maintains the topological invariant that every predecessor state referenced by a transition recurrence is finalized before the dependent state is evaluated. By collapsing identical subtrees of a recursive search graph into O(1) table lookups, DP reduces exponential O(2^n) or factorial O(n!) brute-force complexity to polynomial or pseudo-polynomial time (such as O(n), O(n * W), O(m * n), or O(n^3)).
- Prompts asking for an extremum (minimum cost, maximum profit, longest sequence), total count of ways, or boolean feasibility where local greedy choices fail due to downstream constraints.
- Subset or multiset selection under an integer capacity or target-sum limit (0/1 or unbounded knapsack), where bounds like n <= 1000 and target <= 10^4 admit O(n * target) tabulation.
- Two-sequence comparison, alignment, interleaving, or transformation (strings s1 and s2 of lengths m, n <= 2000), where matching prefixes s1[:i] and s2[:j] yields an O(m * n) grid recurrence.
- Grid routing, tree coverage, DAG pathfinding, or bounded-hop graph traversal where transitions follow a strict partial order (monotone coordinates, post-order subtrees, strictly increasing cell values, or edge budget 1..k + 1).
- Contiguous range or order-dependent elimination problems (n <= 500) where choosing the final operation or split index k inside nums[l..r] partitions the range into independent sub-intervals.
- Sweeping capacity left-to-right in a single-row 0/1 knapsack: updating dp[c] from dp[c - w] in ascending order reads values already updated in the current item's pass, silently turning 0/1 selection into unbounded reuse; iterate c downward or read from an immutable previous row.
- Violating dependency order in interval or goal-anchored DP: reading dp[i + 1][j - 1] or dp[i + 1][j] inside standard ascending row loops accesses uninitialized cells; always loop by increasing substring/interval length or reverse row indices when transitions point to larger row indices.
- Corrupted sentinel values for unreachable states: initializing minimization tables with 0 or maximization tables with 0 when negative profits/scores exist lets invalid branches win min/max comparisons; use +inf (or amount + 1) for minimization, -inf for maximization, and dp[0] = 1 (or True) for counting/reachability seeds.
- Off-by-one character indexing in padded prefix tables: when dp has dimensions (m + 1) x (n + 1) with index 0 representing the empty prefix, state dp[i][j] corresponds to characters s1[i - 1] and s2[j - 1], not s1[i] and s2[j].
def dp_rolling(nums):
if not nums:
return 0
two_back, one_back = 0, nums[0]
for x in nums[1:]:
curr = max(one_back, two_back + x)
two_back, one_back = one_back, curr
return one_backdef knapsack_1d(weights, values, cap, unbounded=False):
dp = [0] * (cap + 1)
for w, v in zip(weights, values):
span = range(w, cap + 1) if unbounded else range(cap, w - 1, -1)
for c in span:
dp[c] = max(dp[c], dp[c - w] + v)
return dp[cap]def prefix_grid_dp(a, b):
m, n = len(a), len(b)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i - 1] == b[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]def interval_dp(nums, cost):
n = len(nums)
dp = [[0] * n for _ in range(n)]
for size in range(1, n + 1):
for l in range(n - size + 1):
r = l + size - 1
for k in range(l, r + 1):
left = dp[l][k - 1] if k > l else 0
right = dp[k + 1][r] if k < r else 0
dp[l][r] = max(dp[l][r], left + cost(l, k, r) + right)
return dp[0][n - 1]