Dynamic Programming

The first mistake interviewers spot is an over‑engineered state. Ask yourself: What must I know to make the next decision? For the classic 0/1 knapsack, the answer is two numbers – the index of the item we are considering and the remaining capacity. Adding the current total value to the state would blow up the table from O(N·W) to O(N·W·V). The same principle applies to string DP: for LCS the state is simply the pair of prefix lengths (i, j). If you include the actual substrings, you turn a linear‑space DP into exponential memory. A minimal state also guarantees that overlapping subproblems truly overlap, which is the prerequisite for memoization. Per the original Bellman definition, DP solves a multistage decision process where each stage’s state fully captures the history needed for future choices. By keeping the state minimal you avoid redundant work and keep the algorithm within the interview’s time limits.

Optimal substructure means the global optimum can be assembled from locally optimal solutions. Formally, if S is an optimal solution for problem P, then for any subproblem p of P, the restriction of S to p must be optimal for p. A quick sanity check: try a counter‑example. Activity selection looks like DP, but a greedy earliest‑finish algorithm is optimal; the DP recurrence would duplicate work because the subproblems are independent once the earliest activity is chosen. Conversely, the coin‑change problem with denominations {1,3,4} fails the greedy test for amount 6 – greedy picks 4+1+1 (3 coins) while DP finds 3+3 (2 coins). Before committing to a DP table, verify overlapping subproblems: compute the same sub‑state from different paths. If each sub‑state is reached only once, a greedy or divide‑and‑conquer approach is likely better. This contrast—use greedy when a locally optimal choice never harms future options; use DP when you need to consider multiple futures—is a decisive interview signal.

The "last decision" viewpoint turns any DP problem into a recurrence. For Fibonacci, the last decision is whether the nth term is computed as fib(n‑1)+fib(n‑2). A top‑down implementation with @lru_cache mirrors the mathematical definition and is trivial to write:

However, for n=10 000 this recursion overflows the Python call stack (see the functools docs). The bottom‑up version eliminates recursion and improves cache locality:

Both run in O(n) time, but the iterative version uses O(1) space and never crashes. The trade‑off is clarity: top‑down is easier to derive and modify during a live interview, while bottom‑up demonstrates awareness of stack limits and performance. Remember to discuss the risk of stack overflow when you first propose memoization.

A 0/1 knapsack with N items and capacity W normally uses a 2D table dp[i][c]. The recurrence dp[i][c] = max(dp[i-1][c], dp[i-1][c-w[i]] + v[i]) only reads the previous row, so we can collapse to a 1‑D array by iterating capacities backward:

Working example: items = [(w=3,v=4),(w=4,v=5)], W=5.
* After first item, dp = [0,0,0,4,4,4].
* After second item, we update c=5→dp[5]=max(4, dp[1]+5)=5, c=4→max(4,dp[0]+5)=5. Final dp[5]=5, the optimal value.
If you need to reconstruct the chosen items, you must keep a predecessor matrix or store a copy of the previous row, because the in‑place 1D version discards that information. Thus space compression is impossible when the interview explicitly asks for the solution set. This nuance often distinguishes a senior candidate.

Three patterns dominate interview DP questions. Knapsack follows a take vs. skip decision; the state is (i, remaining) as shown earlier. Longest Common Subsequence (LCS) uses a 2‑D grid where dp[i][j] stores the LCS length of the first i characters of A and the first j of B. The recurrence:

For strings "ABCBDAB" and "BDCAB", the table fills to 4, and backtracking yields "BCAB". The space can be reduced to O(min(N,M)) by keeping only two rows, as the Wikipedia LCS article notes. Grid path problems (e.g., minimum path sum) have a directional dependency: each cell depends on the top and left neighbors. The DP fills row‑by‑row, and if only the sum is required you can compress to one row. Recognizing which pattern matches your problem saves time: if the decision is binary (take/skip) you’re likely in knapsack territory; if you’re aligning two sequences, think LCS; if movement is constrained to right/down, think grid DP.

Interviewers love to throw empty inputs, single‑element arrays, or negative numbers. A robust DP solution starts with a clear base case table. For knapsack, dp[0][c]=0 for all capacities; for LCS, dp[i][0]=dp[0][j]=0. Forgetting these leads to index errors when the recurrence accesses dp[i-1][c-wi]. When capacities can be zero, the inner loop must start at wi and not run at all otherwise. Negative weights break the classic 0/1 formulation; you either reject them early or shift the problem (e.g., add a constant to make all weights non‑negative). In grid path problems, ensure the starting cell (0,0) is initialized with its own value, and guard the first row/column separately because they have only one predecessor. By stating these initializations out loud you demonstrate thoroughness and avoid the common bug of off‑by‑one errors that cause runtime exceptions.

When the interviewer asks for a DP solution, start by naming the state aloud: "My state is (i, remainingWeight) – the maximum value achievable using the first i items with that remaining capacity." Then prove optimal substructure in one sentence, referencing the earlier section. Next, run a tiny example (e.g., two items, capacity 5) on the whiteboard to show how the table fills; this catches mistakes early. After the example, state the complexity: O(N·W) time, O(W) space after compression, and explain why pseudo‑polynomial (per the Wikipedia knapsack page) is acceptable for interview constraints. Finally, write the code, choosing bottom‑up to avoid stack overflow, and mention that you could switch to memoization if the recurrence were more irregular. End by discussing how you would modify the solution for path reconstruction or for unbounded knapsack, showing depth of understanding.

Implement 0/1 Knapsack for given weights, values, and capacity.

Define dp[c] as the max value for capacity c, iterate items, update dp backwards, O(N·W) time, O(W) space; optionally keep a predecessor array to reconstruct the chosen items.

Find the minimum number of coins to make a target amount (Coin Change).

Use a 1‑D dp where dp[a] = min(dp[a‑coin]+1) for each coin; initialize dp[0]=0 and INF elsewhere. This DP guarantees optimality where greedy fails (e.g., {1,3,4} for amount 6).

Compute the Longest Common Subsequence of two strings.

Build a 2‑D table dp[i][j] with the standard recurrence; compress to two rows for O(min(N,M)) space if only length is needed, and backtrack through the table to output the subsequence.

Determine the minimum path sum from top‑left to bottom‑right in a matrix.

dp[i][j] = grid[i][j] + min(dp[i‑1][j], dp[i][j‑1]); fill row‑wise, O(N·M) time, O(M) space by keeping only the previous row.