Dynamic programming

In short

Dynamic programming (DP) solves a problem by breaking it into overlapping subproblems, solving each subproblem once, and storing the result so it is never recomputed. It applies when a problem has optimal substructure (an optimal solution is built from optimal solutions of subproblems) and overlapping subproblems (the same subproblem recurs many times) — the two conditions that separate DP from plain divide and conquer. In Indian university courses it is the core of "Design and Analysis of Algorithms" (AICTE model curriculum / UGC CBCS), and in GATE CS it is examined as an algorithm design technique with named problems such as LCS, subset sum, 0/1 knapsack and matrix chain multiplication. In placements it is the highest-weight topic after arrays and graphs: Amazon, Microsoft India, Google India, Flipkart, Walmart Global Tech, Goldman Sachs, Zoho, Oracle, Adobe and the service companies' advanced tracks (TCS NQT Digital, Infosys HackWithInfy) all set DP questions in online rounds and on-site interviews.

Explained

What makes a problem a DP problem

• Optimal substructure: the optimal answer for a problem can be written as a function of optimal answers of smaller instances. Formalised as Bellman's principle of optimality (Richard Bellman, 1957, who coined the term "dynamic programming").
• Overlapping subproblems: the recursion tree revisits the same subproblem repeatedly. Naive fib(40) makes 2·F(41)−1 = 331,160,281 calls; DP needs 39 additions.
• If subproblems do not overlap, the right technique is divide and conquer; if a locally best choice is provably globally safe, greedy is cheaper. DP is the fallback when a greedy choice can be shown to fail by counter-example.
• DP is not recursion plus a cache by accident — the cache works only because the subproblem is identified completely by its state. Choosing the state is the whole design problem.
• Counting vs optimising: the same framework answers "how many ways" (sum over transitions), "best value" (min/max over transitions) and "is it possible" (OR over transitions).

Top-down memoisation versus bottom-up tabulation

• Top-down (memoisation): write the natural recursion, add a table initialised to a sentinel (−1, None); on entry, return the stored value if present. Only the states actually reachable are computed.
• Bottom-up (tabulation): fill the table in an order in which every state's dependencies are already filled (increasing index, increasing length, increasing capacity). No recursion stack.
• Order of filling must respect the dependency DAG. For interval DP (MCM, OBST, palindrome partitioning) fill by increasing chain length, not by rows.

How to design a DP in five steps

1. Define the state in words: dp[i][w] = maximum value using the first i items with capacity w. If it cannot be said in one sentence, the state is wrong.
2. Write the transition (recurrence): enumerate every decision at that state and combine with min / max / sum.
3. Fix the base cases, including the empty case and the impossible case (use −∞ for an infeasible maximum, +∞ for an infeasible minimum, 0 for "no ways").
4. Decide the evaluation order (top-down, or bottom-up over the dependency order) and where the answer sits.
5. Reconstruct the solution if asked: either store a parent/choice table, or walk the DP table backwards comparing values (no extra memory).
6. Time = (number of states) × (work per transition); space = number of states, reduced if only the last few rows are needed.

The standard DP families (classification)

• Linear / 1-D DP: Fibonacci, climbing stairs, rod cutting, house robber (max non-adjacent sum), maximum subarray (Kadane), LIS. State = index.
• Knapsack family (subset-selection DP): 0/1 knapsack, subset sum, equal-partition, count-of-subsets, unbounded knapsack, coin change (min coins and number of ways), rod cutting. State = (index, remaining capacity).
• Two-sequence / string DP: LCS, longest common substring, edit (Levenshtein) distance, shortest common supersequence, sequence alignment, wildcard and regex matching, distinct subsequences. State = (i, j) prefixes.
• Interval / partition DP: matrix chain multiplication, optimal binary search tree, palindrome partitioning, burst balloons, minimum cost polygon triangulation. State = (i, j) with a split point k; O(n³) typical.
• Grid DP: unique paths, minimum path sum, gold mine, with obstacles. State = (row, col).
• DP on trees: maximum weight independent set, tree diameter, subtree sums — children computed before the parent by DFS post-order.
• DP over subsets (bitmask DP): travelling salesman O(n²·2ⁿ), assignment problem, minimum set cover, feasible for n ≈ 20.
• Digit DP: count numbers in [L, R] with a digit property; state = (position, carried constraint, tight flag).
• DP on DAGs and graphs: longest path in a DAG, Bellman–Ford and Floyd–Warshall are DP formulations (details in the shortest-paths note).

Classical recurrences in the syllabus

• 0/1 knapsack: each item taken at most once; items are indivisible, so the fractional greedy ratio rule does not give the optimum.
• Unbounded knapsack / coin change: unlimited copies — the same row is reused, so loop capacity in increasing order.
• Min-coin change: greedy works for the Indian coin system (₹1, ₹2, ₹5, ₹10, ₹20) because it is canonical, but fails for arbitrary sets — a standard interview trap.
• LCS: the table is also the basis of diff, git, and DNA alignment; LCS length relates to edit distance with insert/delete only: d = m + n − 2·LCS.
• Edit distance: insert, delete, substitute, each cost 1 (weighted variants appear in exams).
• MCM: finds the cheapest parenthesisation; multiplication is associative so the product is identical, only the cost changes.
• OBST: minimises expected search cost given key probabilities; same O(n³) interval structure (Knuth's optimisation brings it to O(n²)).
• LIS: O(n²) DP, or O(n log n) with binary search on the tails array (patience sorting).
• Subset sum / partition: decide if a subset sums to S; the basis of the balanced-partition and "minimum subset-sum difference" questions.
• TSP (bitmask): dp[mask][i] = cheapest path covering mask and ending at i; exponential but exact.

Complexity, space optimisation and advanced techniques

• Pseudo-polynomial: 0/1 knapsack in O(nW) is polynomial in the value W, not in its number of bits, so knapsack and subset sum remain NP-hard. With W = 10⁹ the table is unusable.
• Rolling array: LCS and knapsack need only the previous row → O(min(m,n)) or O(W) space. For 0/1 knapsack with one array, iterate capacity downwards to avoid reusing an item.
• Matrix exponentiation: any linear recurrence with constant coefficients (Fibonacci, tiling counts) in O(k³ log n) instead of O(n).
• Monotonic deque / sliding-window DP: transitions of the form dp[i] = min(dp[j]) + c over a window drop from O(nk) to O(n).
• Prefix sums inside the transition turn an O(n) sum into O(1) (counting DPs, distinct-subsequence counts).
• Knuth optimisation (O(n³)→O(n²) for OBST-type), divide-and-conquer optimisation and the convex hull trick are contest-level refinements — rarely asked in university exams.
• Modular arithmetic: counting DPs usually ask for the answer mod 10⁹+7; take the modulus at every addition.

Advantages, limitations and comparison

• Advantages: turns exponential recursion into polynomial time; gives the exact optimum (unlike heuristics); the table itself supports reconstruction and sensitivity queries.
• Limitations: memory can dominate (curse of dimensionality — each extra state dimension multiplies the table); needs optimal substructure, so the longest simple path in a general graph has no DP over vertices; the state design is not mechanical.
• Vs greedy: greedy makes one irrevocable choice per step, O(n log n) typically, but needs a proof (exchange argument / matroid); DP tries all choices and is slower but always correct where it applies.
• Vs divide and conquer: D&C partitions into disjoint subproblems (merge sort, binary search); DP's subproblems overlap and must be cached.
• Vs backtracking / branch and bound: both explore the full space; DP collapses identical states, backtracking prunes infeasible ones. Problems with constraints that depend on the path (N-Queens) are not DP.

Key points

• Optimal substructure - the optimum of the whole is composed of optima of parts.
• Overlapping subproblems - the same subproblem is needed many times; caching is what buys the speed-up.
• Principle of optimality - Bellman's statement that any tail of an optimal policy is itself optimal.
• State - the minimal information identifying a subproblem; the table is indexed by it.
• Transition - the recurrence enumerating all decisions at a state.
• Memoisation - top-down recursion with a cache; computes only reachable states.
• Tabulation - bottom-up filling in dependency order; no recursion stack, easy to space-optimise.
• Complexity rule - time = states × transitions per state; space = states (often reducible).
• 0/1 knapsack - O(nW) time, O(W) space; pseudo-polynomial, NP-hard in general.
• LCS - O(mn) time; recurrence 1 + dp[i−1][j−1] on a match, else max(dp[i−1][j], dp[i][j−1]).
• Edit distance - O(mn); min of insert, delete, substitute.
• MCM / OBST - interval DP, O(n³) time and O(n²) space, filled by increasing chain length.
• LIS - O(n²) DP or O(n log n) via binary search on the tails array.
• Bitmask DP - states indexed by subsets, O(2ⁿ·n²) for TSP; practical to n ≈ 20.
• Tree DP - children before parent, computed in DFS post-order.
• Reconstruction - store a choice/parent table, or re-walk the completed table backwards for zero extra memory.
• Greedy fails, DP works - min-coin change with a non-canonical coin set is the canonical counter-example.
• Counting DPs - replace min/max by addition, and take results modulo 10⁹+7.

Formulas and examples

Example 1 — 0/1 knapsack (₹ values, kg weights), capacity W = 8 kg. Items: (2 kg, ₹3), (3 kg, ₹4), (4 kg, ₹5), (5 kg, ₹6) — values in thousands of rupees.

• Sample cell: K[3][7] = max( K[2][7] = 7, 5 + K[2][3] = 5 + 4 = 9 ) = 9.
• Answer ₹10,000. Traceback: K[4][8] = 10 ≠ K[3][8] = 9 → item 4 taken, go to w = 3; K[3][3] = K[2][3] → item 3 not taken; K[2][3] = 4 ≠ K[1][3] = 3 → item 2 taken, w = 0. Items 2 and 4, total 8 kg exactly, ₹10,000.
• The greedy value/weight rule picks item 1 (1.50), then item 2 (1.33); with 3 kg left, item 3 (1.25) and item 4 (1.20) no longer fit, so it stops at 3 + 4 = ₹7,000 — short of the ₹10,000 optimum.

Example 2 — LCS of X = "ABCBDAB" and Y = "BDCAB".

• LCS length = 4. Traceback from the bottom-right taking a diagonal step on every match: B ← A ← C ← B gives "BCAB".
• Cells computed = 7 × 5 = 35; time O(mn) = O(35), against 2⁷ = 128 subsequences of X checked naively.

Example 3 — Matrix chain multiplication. A₁ (5×4), A₂ (4×6), A₃ (6×2), A₄ (2×7); p = [5, 4, 6, 2, 7].

• Length 2: m[1][2] = 5·4·6 = 120; m[2][3] = 4·6·2 = 48; m[3][4] = 6·2·7 = 84.
• m[1][3]: k=1 → 0 + 48 + 5·4·2 = 48 + 40 = 88; k=2 → 120 + 0 + 5·6·2 = 120 + 60 = 180. Min = 88 at k = 1.
• m[2][4]: k=2 → 0 + 84 + 4·6·7 = 84 + 168 = 252; k=3 → 48 + 0 + 4·2·7 = 48 + 56 = 104. Min = 104 at k = 3.
• m[1][4]: k=1 → 0 + 104 + 5·4·7 = 104 + 140 = 244; k=2 → 120 + 84 + 5·6·7 = 204 + 210 = 414; k=3 → 88 + 0 + 5·2·7 = 88 + 70 = 158. Min = 158 at k = 3.
• Answer: 158 scalar multiplications, parenthesised ((A₁(A₂A₃))A₄). The worst order (414) costs 2.6× more for the same product.

Example 4 — coin change, both variants.

• (a) Min coins for 6 with denominations {1, 3, 4}: C[0]=0, C[1]=1, C[2]=2, C[3]=1, C[4]=1, C[5] = 1 + min(C[4], C[2], C[1]) = 1+1 = 2, C[6] = 1 + min(C[5]=2, C[3]=1, C[2]=2) = 2 (3+3). Greedy takes 4 then 1 then 1 = 3 coins — proof that greedy is wrong for a non-canonical set.
• (b) Number of ways to make ₹10 from ₹1, ₹2, ₹5 coins (order irrelevant): two ₹5 → 1 way; one ₹5 + ₹5 from {1,2} → 3 ways (0, 1 or 2 twos); no ₹5 + ₹10 from {1,2} → 6 ways (0–5 twos). Total = 10 ways. The DP table W[c][a] with 3 rows and 11 columns gives the same 10 at W[3][10].

Example 5 — LIS of [10, 22, 9, 33, 21, 50, 41, 60, 80].

• dp = [1, 2, 1, 3, 2, 4, 4, 5, 6] → length 6, one witness being 10, 22, 33, 50, 60, 80.
• O(n log n) method, tails array after each element: [10] → [10,22] → [9,22] → [9,22,33] → [9,21,33] → [9,21,33,50] → [9,21,33,41] → [9,21,33,41,60] → [9,21,33,41,60,80] → length 6. The tails array is not itself an LIS, only its length is meaningful.

# 0/1 knapsack, O(nW) time, O(W) space. Capacity loop runs DOWNWARD.
def knapsack(wt, val, W):
    dp = [0] * (W + 1)
    for i in range(len(wt)):
        for w in range(W, wt[i] - 1, -1):
            dp[w] = max(dp[w], val[i] + dp[w - wt[i]])
    return dp[W]

# Memoisation pattern (top-down). lru_cache replaces a hand-written dict.
from functools import lru_cache
def lcs(x, y):
    @lru_cache(maxsize=None)
    def f(i, j):
        if i == 0 or j == 0: return 0
        if x[i-1] == y[j-1]: return 1 + f(i-1, j-1)
        return max(f(i-1, j), f(i, j-1))
    return f(len(x), len(y))

Where it is used

• Product engineering and interviews: Amazon, Microsoft IDC, Google India, Flipkart, Walmart Global Tech, Adobe, Zoho, Oracle and fintechs (Razorpay, PhonePe, Zerodha) test DP in online assessments; HackerRank, HackerEarth, CodeChef and InterviewBit rounds used by Indian recruiters are built around these recurrences.
• Logistics and e-commerce: container, truck and carton loading at Delhivery, Blue Dart, Flipkart and Amazon India is a knapsack/bin-packing problem; route and slot assignment uses DP over subsets or DP on DAGs for small instances.
• Bioinformatics and health informatics: Needleman–Wunsch global and Smith–Waterman local alignment are the LCS/edit-distance DP with gap penalties — used in genomics labs (CSIR-IGIB, NIBMG) and in BLAST-style pipelines.
• Text, search and Indian-language NLP: spell correction and fuzzy name matching (edit distance) in Aadhaar-style demographic matching, railway and banking name search; diff and git merge use LCS; the Viterbi algorithm (DP over HMM states) underlies speech recognition and part-of-speech tagging for Hindi and other Indian languages.
• Operations research and power systems: unit commitment and hydro-thermal scheduling at state load despatch centres have classic DP formulations (now usually solved by MILP solvers); inventory and capacity planning use the same stage-wise recursion.
• Reinforcement learning and control: value iteration and policy iteration are the Bellman equation solved by DP — the base layer under pricing, ad bidding and ride-matching engines at Ola, Uber India, Swiggy and Zomato.

Interview questions

• Q: What two properties must a problem have for DP to apply? A: Optimal substructure and overlapping subproblems. Without overlap, divide and conquer is enough; without optimal substructure, DP's recurrence is simply wrong.
• Q: Difference between memoisation and tabulation? A: Memoisation is top-down recursion with a cache and computes only reachable states; tabulation is bottom-up in dependency order, avoids the call stack and is easier to space-optimise.
• Q: Why is 0/1 knapsack still called NP-hard if it runs in O(nW)? A: Because O(nW) is pseudo-polynomial — W is a numeric value, and its input size is log W bits, so the running time is exponential in the input length.
• Q: When does greedy beat DP, and when does it break? A: Greedy is correct and faster when a local choice is provably safe (fractional knapsack, activity selection); it breaks on 0/1 knapsack and on min-coin change with non-canonical denominations such as {1, 3, 4} for 6.
• Q: In the space-optimised 1-D 0/1 knapsack, why iterate capacity downwards? A: Going upwards would read a value already updated in the same item's pass, which would allow the item to be used more than once — that is the unbounded knapsack.
• Q: Why is MCM filled by increasing chain length rather than row by row? A: m[i][j] depends on m[i][k] and m[k+1][j], which are shorter chains; only a length-wise order guarantees they are ready.
• Q: How do you recover the actual LCS, not just its length? A: Walk back from L[m][n]: on a character match step diagonally and emit the character, otherwise move to the larger of L[i−1][j] and L[i][j−1]; reverse the collected string.
• Q: State the LIS O(n log n) idea. A: Keep an array of the smallest possible tail for each length and binary-search each new element to replace the first tail ≥ it (lower_bound); the array's final length is the LIS length, though the array itself may not be a valid subsequence.
• Q: How large can n be for a bitmask DP? A: Around 20–22, since 2ⁿ·n² work and n·2ⁿ memory grow fast — 2²⁰ ≈ 10⁶ states is fine, 2³⁰ is not.
• Q: Can DP find the longest simple path in a general graph? A: No — a vertex-indexed state loses the set of already-visited vertices, so optimal substructure fails. It works on a DAG, or with a bitmask state for small n.
• Q: How does the knapsack DP change if items may be taken fractionally? A: DP is unnecessary; sort by value per unit weight and fill greedily, which is O(n log n) and provably optimal.
• Q: Why do counting DPs ask for the answer modulo 10⁹+7? A: The counts overflow 64-bit integers quickly; 10⁹+7 is prime, keeps every intermediate below ~10¹⁸ when multiplied, and allows modular inverses.

Common mistakes

• Wrong or incomplete state: leaving out a dimension the transition actually depends on (remaining capacity, last chosen index, parity), so the cache returns an answer computed under different constraints.
• Bad base cases: using 0 instead of +∞ for an infeasible minimum, which silently reports a nonexistent solution — the classic coin-change bug.
• Filling in the wrong order: reading a cell not yet computed (row-wise MCM, or forward iteration in 1-D 0/1 knapsack, which turns it into unbounded).
• Confusing problem variants: longest common *substring* (contiguous, reset to 0 on a mismatch) with longest common *subsequence*; 0/1 with unbounded knapsack; "count ways" where order matters with where it does not.
• Quoting O(nW) as polynomial in an exam answer on complexity classes, or claiming DP proves knapsack is in P.
• Off-by-one on 1-indexed tables: comparing x[i] with y[j] when the table rows mean prefixes of length i (it must be x[i−1] and y[j−1]).
• Recursion depth and memory: deep memoised recursion overflowing Python's default limit, or allocating an O(mn) table when a rolling row would do — the common cause of MLE/TLE verdicts in placement tests.

Related topics

• Recursion and backtracking · Greedy algorithms · Divide and conquer · Time and space complexity · Graph algorithms: BFS, DFS and shortest paths · DSA interview patterns