Technical interview guide

2-D Dynamic Programming

DP where the subproblem needs two indices — grid paths, two-string comparisons, and knapsack-style capacity constraints.

Read: 46 min
Practice MCQs: 25
Interview QA: 25
Edition: v7
Editorial status: Reviewed
Relevant for: AI EngineerBackend EngineerBlockchain DeveloperComputational BiologistData ScientistEmbedded Systems EngineerFrontend EngineerFull-Stack DeveloperMachine Learning EngineerQuantum Software EngineerRobotics EngineerSoftware Engineer

Scope: Language-neutral, with memoisation and recursion behaviour cited from CPython 3.14.

Interview QA

Treat each question like a live interview question: answer out loud first (structure, assumptions, tradeoffs), then open the model answer to spot gaps and rehearse a tighter follow-up.

Curated: 2026-10-03 · Written: 2026-10-03 · Reviewed: 2026-10-03

QA-1

When does a dynamic program need a second state dimension, and how do you decide what the second index should encode?

QA-2

How do you derive the grid-path counting recurrence, and how far can you reduce the space? Walk me through the state, the recurrence, the base cases, one small grid you compute by hand, and what the loop order must preserve when you go to O(n).

QA-3

Walk through obstacles and unreachable cells, including where engineers most often get it wrong.

QA-4

What does minimum-cost paths guarantee, and what does it deliberately leave open?

QA-5

How do you build the LCS table, reconstruct one actual subsequence from it, and handle ties — and what changes for longest common substring?

QA-6

How do you derive the edit-distance recurrence, and how do you cut the table to two rows? Walk me through the state, the insert/delete/replace branches, the base cases, one small worked example, and what has to be carried across iterations.

QA-7

Where does weighted edit operations matter, and where is it irrelevant?

QA-8

Teach the zero-one knapsack table to an engineer who has only seen it as a rule of thumb.

QA-9

How do you collapse the 0/1 knapsack table to a single array? Walk me through what dp[w] means, why the capacity loop runs backwards for 0/1 items and forwards for unbounded, what breaks if you flip it, and the resulting complexity.

QA-10

Given an array of positive integers, can it be partitioned into two subsets with equal sum? Walk me through the 2-D DP state, the take/skip recurrence, base cases, where the answer is read, the complexity, and how you report that no equal partition exists.

QA-11

Explain interval dynamic programming on matrix chain multiplication — what is the state, what is the transition, and in what order do you fill the table?

QA-12

How does matrix-chain multiplication change if the workload grows by two orders of magnitude?

QA-13

Count the palindromic substrings of a string with a 2-D DP and reuse the same table for the longest palindromic substring. Walk me through the state, recurrence, base cases, loop order, complexity, and when expand-around-centre is the better answer.

QA-14

Memory is the binding constraint on a 2-D DP: how do you decide which dimension to roll away, which loop direction keeps the surviving row valid, and when must you keep the full table?

QA-15

Walk me through the 2-D DP for wildcard matching with '?' and '' (LeetCode 44): the state dp[i][j], the literal/'?' transition, both '' branches, the empty-string and empty-pattern base cases including a leading run of '*', the off-by-one convention, and the O(mn) cost.

QA-16

When a 2-D DP transition carries a cost — a weight, penalty or per-move charge — where in the recurrence should it be applied, and what characteristic wrong answer do you get if it's counted twice or left out?

QA-17

When can a 2-D DP transition be accelerated with a monotonic deque, and how do you argue the optimisation preserves the exact optimum? What is the structural condition on the transition, how is the deque maintained across one dimension, and what counterexample shows it is invalid?

QA-18

In a 2-D DP over a large sparse state space, when does top-down memoisation stop being the convenient choice, and what are the concrete remedies?

QA-19

Given a filled 2-D DP table, how do you reconstruct one optimal solution from it — and what changes when you need every optimal solution, or only the value?

QA-20

What trade-off does hirschberg's reduction force that a junior answer usually skips?

QA-21

When is top-down memoization preferred over bottom-up tabulation in 2-D DP, and how does sparsity in the state space change memory and time complexity?

QA-22

What is the smallest experiment that would change your mind about recursion depth in two dimensions?

QA-23

How does index conventions interact with rollback, and where do people ignore that?

QA-24

When you reconstruct the optimal choices from a filled 2-D DP table, when do you re-derive the transition on the walk back instead of storing parent pointers, and what does each approach cost?

QA-25

When you formulate a 2-D DP, when do you index states by input indices (prefix/suffix) versus by an auxiliary parameter like remaining capacity or budget?