Skip to content

Topic 18 of 20

Dynamic Programming – 2D & Advanced

Grids, two-string DP, stock state machines, interval DP and bitmask DP.

30 problems0 Easy19 Medium11 Hard

The concept

When one index is not enough to describe a subproblem, the DP state grows a second dimension. In grid DP, dp[r][c] is the answer for reaching cell (r, c), built from its neighbours. In two-string DP, dp[i][j] describes the first i characters of one string and the first j of another. That single idea powers Longest Common Subsequence, Edit Distance, Distinct Subsequences and regular-expression matching.

Some problems are best seen as a state machine: in the stock-trading series, each day you are either holding, not holding or in a cooldown, and each state transitions to the next day's states. Interval DP defines dp[l][r] over a subarray and tries every split point, as in Burst Balloons and cutting sticks. Bitmask DP encodes a set of chosen items as the bits of an integer, which makes "assign each of n ≤ 20 things" problems tractable.

Always draw the table, fill a small example by hand, and look for the direction of dependencies. It tells you the loop order and whether you can reduce memory to one or two rows.

Patterns you will learn

Problems, in order

  1. 1

    The simplest grid DP.

    Grid PathsReported at: GoogleMetaMicrosoft+4
  2. 2

    Grid DP with obstacles.

    Grid PathsReported at: MetaAmazonGoogle+3
  3. 3

    Minimising cost across a grid.

    Grid PathsReported at: AmazonMicrosoftGoogle+4
  4. 4
    TriangleMedium

    Bottom-up from the last row with O(n) space.

    Grid Paths (Bottom-up)Reported at: AmazonMicrosoft
  5. 5

    Row-to-row transitions with three parents.

    Grid PathsReported at: Google
  6. 6

    The min-of-three-neighbours recurrence.

    Grid DPReported at: MicrosoftGoogleAmazon+4
  7. 7

    The same recurrence, used for counting.

    Grid DPReported at: GoogleBloomberg
  8. 8

    The foundational two-string DP.

    Two-string DP (LCS / Edit Distance)Reported at: AmazonDoorDashBloomberg
  9. 9

    Reduces directly to LCS.

  10. 10

    Insert, delete and replace transitions; a top Google question.

    Two-string DP (LCS / Edit Distance)Reported at: AmazonMicrosoftGoogle+4
  11. 11

    Two-pointer state on two strings.

    Two-string DPReported at: AmazonAppleGoogle+2
  12. 12

    LCS with the reversed string, or interval DP.

    Interval DPReported at: AmazonMicrosoftApple+3
  13. 13
  14. 14

    The same state machine with a fee.

    State Machine DPReported at: AmazonMeta
  15. 15

    A knapsack with two capacity dimensions.

    2D KnapsackReported at: Apple
  16. 16

    Reduces to closest subset sum.

  17. 17

    Counting ways over (dice, sum) states.

  18. 18

    DP over (moves, row, column).

    Counting DP over MovesReported at: Amazon
  19. 19

    Minimax DP on intervals, plus a maths shortcut.

    Game DPReported at: Amazon
  20. 20

    Counting subsequence matches.

    Two-string DP (Counting)Reported at: AmazonGoogle
  21. 21

    The '*' transitions are a classic Hard.

    Two-string DPReported at: MetaMicrosoftGoogle+6
  22. 22

    A close cousin of regex matching.

    Two-string DPReported at: MicrosoftAmazonGoogle+2
  23. 23

    Two-transaction state machine.

    State Machine DPReported at: AmazonAppleUber
  24. 24

    Generalised to k transactions.

    State Machine DPReported at: AmazonAppleGoogle+1
  25. 25

    Choose the *last* balloon to burst; the defining interval DP.

    Interval DPReported at: GoogleMicrosoftApple+3
  26. 26

    Interval DP over cut positions.

  27. 27

    Palindrome table plus a minimum-cuts DP.

    Interval DP + 1D DPReported at: Amazon
  28. 28

    Solve from the end because the constraint flows backward.

    Grid Paths (Reverse)Reported at: AmazonUber
  29. 29

    Two agents moving simultaneously share one state.

  30. 30

    Set cover over skills encoded as bitmasks.