Dynamic Programming
Dynamic programming (DP) is an algorithmic technique that solves complex problems by breaking them into overlapping sub-problems, solving each sub-problem ...
Core Principles of Dynamic Programming
Dynamic programming (DP) is an algorithmic technique that solves complex problems by breaking them into overlapping sub-problems, solving each sub-problem exactly once, and storing its result to avoid redundant computation. It applies when a problem has two properties: overlapping sub-problems (the same sub-problems recur many times) and optimal substructure (an optimal solution contains optimal solutions to sub-problems).
The name "dynamic programming" was coined by Richard Bellman in the 1950s as a politically neutral term to describe his mathematical work — he wanted to avoid words like "research" or "mathematics" that were unfashionable with his funding agency. Despite the name, the technique is purely about structured recursion with storage.
DP differs from divide-and-conquer in one critical way: divide-and-conquer sub-problems do not overlap (merge sort splits into completely independent halves), while DP sub-problems do overlap (Fibonacci(5) calls Fibonacci(4) and Fibonacci(3), and Fibonacci(4) also calls Fibonacci(3)). Without memoization, this overlap causes exponential redundancy.
A worked example: computing Fibonacci numbers. The naive recursive approach computes Fibonacci(50) in O(2^50) time because each call spawns two sub-calls and duplicates work. Adding memoization reduces this to O(n) time and O(n) space by caching each computed value. Tabulation achieves the same O(n) time with O(1) space if you only keep the last two values.
Interview tip: When you recognize overlapping sub-problems, immediately tell the interviewer you see the DP structure. Then state whether you will use top-down memoization or bottom-up tabulation, and explain why. Demonstrating that you choose deliberately — not arbitrarily — impresses interviewers.
Identifying DP Problems and Defining States
The hardest part of dynamic programming is not writing the recurrence — it is recognizing that DP applies and defining the right state. A state captures exactly the information needed to make future decisions without knowing how you reached the current situation. Poorly chosen states lead to either incorrect solutions or unnecessarily large tables.
Common signals that a problem benefits from DP: the problem asks for a minimum, maximum, count, or existence ("can we achieve X?"); the solution involves making sequential choices where earlier choices affect later options; the input is a string, array, or sequence and you process it left to right; or the problem mentions words like "subsequence," "partition," "schedule," or "path."
State definition strategy: identify what changes as the problem recurses. For a knapsack with n items and capacity W, the remaining items and remaining capacity define the state: dp[i][w] = maximum value using items 1..i with remaining capacity w. For a string problem like longest common subsequence, the state is two indices, one into each string: dp[i][j] = LCS length of the first i characters of string A and first j characters of string B.
Once the state is defined, write the recurrence by considering all choices at the current state and taking the optimal result. Always handle base cases explicitly: what is the answer for an empty input, zero capacity, or zero length? Base cases are the foundation on which the recurrence rests.
Interview tip: Before writing any code, spend thirty seconds describing your DP state and recurrence in plain English. Saying "dp[i][j] represents the minimum cost to process the first i elements with j units remaining, and we transition by either including or skipping element i" gives the interviewer a clear view of your thought process and makes your code easier to follow.
Reconstructing Solutions from DP Tables
Dynamic programming problems often ask not just for the optimal value but also for the actual solution — the specific items chosen, the specific path taken, or the specific sequence selected. Reconstructing this solution from a completed DP table requires a backtracking pass that traces the decisions that led to each optimal value.
The standard approach: after filling the DP table, start from the cell representing the full problem (e.g., dp[n][W] for the knapsack) and work backwards. At each cell, determine which choice was made to arrive at that value. For the knapsack: if dp[i][w] == dp[i-1][w], item i was skipped; if dp[i][w] == dp[i-1][w - weight[i]] + value[i], item i was included. Move to the appropriate predecessor cell and repeat until you reach a base case.
For some problems, reconstructing the solution requires storing not just the optimal value but also the choice made at each state. A parent or choice table records, for each (i, j), which direction the transition came from. String alignment (edit distance) uses exactly this: a three-directional choice table (match/mismatch, insert, delete) lets you reconstruct the alignment by following arrows back to (0, 0).
Space optimization is sometimes possible: if you only need the optimal value, you can reduce a 2D table to two rows (current and previous), cutting O(n*m) space to O(m). However, this destroys the reconstruction path, so if you need the actual solution, you must keep the full table or use divide-and-conquer DP for a O(n log n) space-efficient reconstruction.
Interview tip: Always ask the interviewer "do you need just the optimal value, or also the actual solution?" This shows awareness that reconstruction changes the algorithm's space requirements, and it prevents you from writing extra reconstruction code if it is unnecessary.