Dynamic Programming: Intermediate

Two dimensions, two sequences, one table. Master 2D DP and you can solve anything.

Two dimensions, two sequences, one table. Master 2D DP and you can solve anything.

Category

Python

Difficulty

intermediate

Duration

35 minutes

Challenges

0 hands-on challenges

Topics covered: 2D DP: Grid Problems, Knapsack Variants: Include or Exclude, LCS and Edit Distance, DP on Strings, Interval DP

Lesson Sections

1. 2D DP: Grid Problems (concepts: py2DDP, pyGridDP, pyRollingRow)

   Grid DP problems give you an m x n grid and ask you to move from top-left to bottom-right (usually only right or down). dp[i][j] represents 'the answer at cell (i, j).' Because you can only move right or down, dp[i][j] depends only on dp[i-1][j] (came from above) and dp[i][j-1] (came from left). Fill the table row by row, left to right. This structure is so regular that once you have solved unique paths, minimum path sum falls out in minutes. Unique Paths (LeetCode 62) Count the number of distin

2. Knapsack Variants: Include or Exclude (concepts: pyKnapsack, pySubsetSum, pyCoinChange)

   Knapsack problems are the purest expression of the include/exclude DP paradigm. At each item, you make a binary decision: include it or exclude it. That decision plus the answer for remaining items and remaining capacity gives you the recurrence. Every knapsack variant, 0/1, unbounded, subset sum, multiple knapsack, is a variation on this single idea. Master the paradigm, not the individual problems. 0/1 Knapsack n items, each with weight w[i] and value v[i]. A bag with capacity W. Maximize tota

3. LCS and Edit Distance (concepts: pyLCS, pyEditDistance, pyRecordLinkage)

   Longest Common Subsequence and edit distance are the two most important 2D DP problems for data engineering interviews. They are not just algorithm exercises. They are the foundation of diff tools, schema reconciliation, log pattern matching, and record linkage. If you can implement both from scratch and explain the DE applications, you are answering at the senior level. Longest Common Subsequence (LeetCode 1143) Given two strings s1 and s2, find the length of their longest common subsequence (n

4. DP on Strings (concepts: pyStringDP, pyPalindromeDP, pyInterleave)

   String DP problems are a class of 2D DP where dp[i][j] represents 'the answer for the substring or prefix ending at index i of one string and index j of another (or the same) string.' The table is always (n+1) x (n+1) or (m+1) x (n+1). The fill pattern is always left-to-right, top-to-bottom. What changes is the transition: what does it mean when characters match, and what do you do when they do not? Palindrome Substrings (LeetCode 647) Count all palindromic substrings. dp[i][j] = True if s[i..j]

5. Interval DP (concepts: pyIntervalDP, pyMatrixChain, pyBurstBalloons)

   Interval DP is a specialized form of 2D DP where dp[i][j] represents 'the optimal cost for the subproblem over the interval [i, j].' The key insight: the optimal answer for a large interval is built from optimal answers for smaller intervals. You always iterate by increasing interval length. This is the opposite of grid DP (which fills row by row). The subproblems are not prefixes; they are intervals. Matrix chain multiplication and burst balloons are the canonical examples. Burst Balloons (Leet