menu_bookGyanByte
Practice SetLesson 181 min read

Dynamic Programming II (2-D) — Practice Problems

November 05, 2026

// How to use this set

When the state needs two indices (two sequences, or a grid), fill a 2-D table where each cell comes from its neighbours. Medium: Unique Paths I & II, Minimum Path Sum, Longest Common Subsequence, Edit Distance, Maximal Square, Longest Palindromic Substring & Subsequence, Interleaving String. Hard: Distinct Subsequences, Dungeon Game, Regular Expression Matching. Get the full 2-D version right first, then compress to one row. Every solution below was run and tested.

Twelve problems that drill 2-D dynamic programming from Lesson 18 — two-sequence tables and grid DPs. The recurrence is still the whole game, there’s just one more index. Open a problem, try it yourself first, then read how to reach the solution. Each solution here was actually run and tested.

How to practise. Draw the table for a tiny example by hand before coding — three or four cells is enough to confirm the recurrence and the base row/column. Get the full 2-D version correct first; only then compress to a single rolling row (and watch the iteration direction).

The 12 problems

  1. 1Unique Paths (LeetCode 62)MediumCount right/down paths across an m×n grid: each cell is the sum of the cell above and the cell to its left.arrow_forward
  2. 2Unique Paths II (LeetCode 63)MediumCount right/down paths through a grid with obstacles: same up + left recurrence, but blocked cells hold 0.arrow_forward
  3. 3Minimum Path Sum (LeetCode 64)MediumCheapest right/down path through a grid of costs: each cell adds its cost to the cheaper of above and left.arrow_forward
  4. 4Longest Common Subsequence (LeetCode 1143)MediumLength of the longest subsequence two strings share: on a match extend the diagonal, else drop a character.arrow_forward
  5. 5Edit Distance (LeetCode 72)MediumFewest inserts, deletes and replaces to turn one word into another: a two-string DP table.arrow_forward
  6. 6Maximal Square (LeetCode 221)MediumArea of the largest all-1 square in a binary matrix: each cell's square is min(up, left, diagonal) + 1.arrow_forward
  7. 7Longest Palindromic Substring (LeetCode 5)MediumLongest palindrome inside a string: expand outwards from each of the 2n-1 centres and keep the widest.arrow_forward
  8. 8Longest Palindromic Subsequence (LeetCode 516)MediumLongest palindrome you can form by deleting characters: an interval DP on matching ends.arrow_forward
  9. 9Interleaving String (LeetCode 97)MediumIs s3 a merge of s1 and s2 that keeps each one's order? dp over prefix pairs, compressed to one row.arrow_forward
  10. 10Distinct Subsequences (LeetCode 115)HardCount the ways t appears as a subsequence of s: dp[j] counts ways to form t[:j], updated right to left.arrow_forward
  11. 11Dungeon Game (LeetCode 174)HardMinimum starting health to cross a grid of damage and potions: fill the DP backwards from the princess.arrow_forward
  12. 12Regular Expression Matching (LeetCode 10)HardMatch a string against a pattern with '.' and '*': dp[i][j] over prefixes, where x* means zero or more x.arrow_forward
coding-interviewdynamic-programmingdp2dleetcodepythonpractice
arrow_back Back to the lessonDynamic Programming II — 2-DNext lesson arrow_forwardData Structures: Your Toolbox