2D DP

Mental model

2D dynamic programming fills a table where each cell depends on a few neighbors (often the ones above and to the left). The hard part is naming the state precisely — once dp[i][j] has a clear one-sentence meaning, the recurrence usually falls out.

How to study 2D DP

Begin by restating the mental model in your own words, then connect it to a concrete system you have built or operated. Name the mechanism, the constraint it addresses, and the trade-off it introduces. Use Dynamic programming (Wikipedia), MIT 6.006 L21 — DP III: Parenthesization, Edit Distance, Knapsack, Knapsack problem (cp-algorithms) to check details, but close the source before writing your explanation. Retrieval is the learning step; rereading is only preparation.

Next, compare 2D DP with the neighboring concepts in its roadmap. Ask what changes in correctness, latency, resource use, operability, and failure recovery. Complete Minimum path sum in a grid and preserve the command, input, output, and one failed attempt as evidence. Finish by explaining the idea without jargon to someone who has not studied the track.

Proof of understanding

• Explain the mechanism from first principles and identify the state it reads or changes.
• Give one situation where the concept is the right choice and one where it is not.
• Predict a realistic failure mode before running the drill, then compare the prediction with evidence.
• Connect the result to a roadmap or build artifact instead of treating the concept as isolated trivia.

Learn from primary sources

• Dynamic programming (Wikipedia) (doc)
• MIT 6.006 L21 — DP III: Parenthesization, Edit Distance, Knapsack (video)
• Knapsack problem (cp-algorithms) (doc)

Practice and explain it back

Review prompts

• In edit distance, state precisely what dp[i][j] means and what the three predecessor cells correspond to.

Build evidence

Use a roadmap capstone to turn this concept into working evidence.

Learning paths

• DSA Practice