Topic 16: 2D DP

Key-Intuition: Two-dimensional dynamic programming handles problems with sequences compared across two indices, often strings or grids.

Canonical Question Types #

Expect to have some overlaps with DP1 topic.

Sequence Alignment (LCS, Substring, Palindrome) #

Compare strings for commonalities, optimal matchings

Problems #

Longest Common Subsequence (1143) This just deals with prefixes and we build up to the eventual strings that we are comparing. It’s definitely 2D because of the 2 Strings and dp[i][j] is the LCS between strings text1[:i] and text2[:j] and our answer will be at dp[len(text1) + 1][len(text2) + 1]. We can do this recursively or iteratively and the iterative solution also has a space-optimised 1D rolling approach we can take.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
    # M1: recursive solution:
    from functools import cache
    class Solution:
        def longestCommonSubsequence(self, text1: str, text2: str) -> int:

            @cache
            def helper(first_idx, second_idx):
                if first_idx < 0 or second_idx < 0:
                    return 0

                is_last_same = text1[first_idx] == text2[second_idx]
                if is_last_same:
                    return 1 + helper(first_idx - 1, second_idx - 1)
                else:
                    return max(helper(first_idx - 1, second_idx), helper(first_idx, second_idx - 1))

            return helper(len(text1) - 1, len(text2) - 1)

    # M2: most efficient, space optimised bottom up approach using a 1D rolling array
    class Solution:
        def longestCommonSubsequence(self, text1: str, text2: str) -> int:
            m, n = len(text1), len(text2)
            dp = [0] * (n + 1)  # dp[j] = LCS length for text1 prefix up to i and text2 prefix up to j

            for i in range(1, m + 1):
                prev = 0  # This will hold dp[j-1] from previous iteration (the previous diagonal)
                for j in range(1, n + 1):
                    temp = dp[j]  # Save current dp[j] which will become prev in next iteration
                    # case 1: the two are the same characters => both of them should be in
                    if text1[i - 1] == text2[j - 1]:
                        dp[j] = prev + 1
                    # case 2: the two are different, we either include this or exclude this, whichever is better
                    else:
                        dp[j] = max(dp[j], dp[j - 1])
                    prev = temp  # Update prev for next j
            return dp[n]

    # M2: not optimised space 2D approach to  2D problem -- but it will pass all test cases.
    class Solution:
        def longestCommonSubsequence(self, text1: str, text2: str) -> int:
            # dp[i][j] -> LCS between strings text1[:i] and text2[:j]
            # answer will be at dp[len(text1)][len(text2)]
            # dp = [[[0] * (len(text1) + 1)] for j in range(len(text2) + 1)]
            dp = [[0] * (len(text2) + 1) for _ in range(len(text1) + 1)]


            for i in range(len(text1)):
                for j in range(len(text2)):
                    # is same letter:
                    if text1[i] == text2[j]:
                        dp[i + 1][j + 1] = 1 + dp[i][j]

                    else: # get max of adjacent builds
                        dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])

            return dp[len(text1)][len(text2)]
            # this shows us how we could have just used a rolling 1D array because of the state transitions that we see above.

    # M3: not perfect but 2 1D arrays for a 2D DP solution:
    class Solution:
        def longestCommonSubsequence(self, text1: str, text2: str) -> int:
            m, n = len(text1), len(text2)
            # Use only two rows
            prev = [0] * (n + 1)
            curr = [0] * (n + 1)
            for i in range(1, m + 1):
                for j in range(1, n + 1):
                    if text1[i - 1] == text2[j - 1]:
                        curr[j] = prev[j - 1] + 1
                    else:
                        curr[j] = max(prev[j], curr[j - 1])
                prev, curr = curr, prev  # Roll rows (no need to clear curr due to overwrite)
            return prev[n]

The space optimisations are nifty but we can pass thigns without it, the 2D DP approach is sufficient. Just to be clear, this is not similar to Longest Increasing sequence (in which it’s more about within one array and this is about commonality / sequence alignment checks.)

Longest Palindromic Substring (5)
Palindromic Substrings (647)

Edit Distance and String Transformation #

Minimize cost (insert/delete/replace) to convert string

Problems #

Edit Distance (72)

We have some defined types of operations that we can do (insert, delete, replace), with strings it’s always a good idea to just consider building up from smaller subproblems and the smaller subproblems is usually defined as string prefixes (and we build them up). This naturally gives a 2D table, which we can then look for space optimisations for.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
    # without space optimsation, 2D table:
    class Solution:
        def minDistance(self, word1: str, word2: str) -> int:
            n, m = len(word1), len(word2)

            # dp[i][j] shows min number of operations to use to convert word1[:i] to word2[:j]
            dp = [[0] * (m + 1) for _ in range(n + 1)]

            for i in range(n + 1):
                dp[i][0] = i # delete all from word1 to get empty word2

            for j in range(m + 1) :
                dp[0][j] = j # insert all to convert empty word1 to word2[:j]

            for i in range(1, n + 1): # because these are exclusive slice params
                for j in range(1, m + 1):
                    if word1[i - 1] == word2[j - 1]:
                        dp[i][j] = dp[i - 1][j - 1]
                    else:
                        insertion = dp[i][j - 1] + 1
                        deletion = dp[i - 1][j] + 1
                        replacement = dp[i - 1][j - 1] + 1
                        dp[i][j] = min(insertion, deletion, replacement)

            return dp[n][m]
    # space optimisations with 2 rolling rows:
    class Solution:
        def minDistance(self, word1: str, word2: str) -> int:
            n, m = len(word1), len(word2)
            if n < m:
                # ensure n >= m to use less space
                return self.minDistance(word2, word1)

            previous_row = list(range(m + 1))
            current_row = [0] * (m + 1)

            for i in range(1, n + 1):
                current_row[0] = i
                for j in range(1, m + 1):
                    if word1[i - 1] == word2[j - 1]:
                        current_row[j] = previous_row[j - 1]
                    else:
                        insert_op = current_row[j - 1] + 1
                        delete_op = previous_row[j] + 1
                        replace_op = previous_row[j - 1] + 1
                        current_row[j] = min(insert_op, delete_op, replace_op)

                # swap them
                previous_row, current_row = current_row, previous_row


            return previous_row[m]

The idea for the space optimisation comes from the fact that we just need to keep track of 2 rows from our state transitions that we observe – pretty much a snapshot approach.

Regular Expression Matching (10)

Distinct Subsequences & Pattern Matching #

Counting how many ways a pattern appears as (possibly non-contiguous) subsequence

Problems #

Distinct Subsequences (115)

We can initially think of this as a 2 pointer region and counting problem which would give us a 2D table (dp[i][j] is number of ways to make t[:j] from s[:i] (prefixes)), and then look for space optimisations.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
    # WITHOUT SPACE OPTIMISATION
    class Solution:
        def numDistinct(self, s: str, t: str) -> int:
            n, m = len(s), len(t)

            if n < m:
                return 0

            # dp[i][j] shall represent the number of ways to make t[:j] from s[:i]
            dp = [[0] * (n + 1) for _ in range(m + 1)]

            # all the 0 length can be fromed from any prefix of s
            for j in range(n + 1):
                dp[0][j] = 1

            # for the target:
            for i in range(1, m + 1):
                # for the source
                for j in range(1, n + 1):
                    if s[j - 1] == t[i - 1]:
                        # on last char match, we take:
                        # A: ways without current char in s (dp[i][j-1])
                        # B: ways using the current matching char (dp[i-1][j-1])
                        dp[i][j] = dp[i][j - 1] +  \
                                   dp[i - 1][ j - 1] # ans to the prev letter
                    else:
                        dp[i][j] = dp[i][j - 1]

            return dp[m][n]

    # WITH SPACE OPTIMISATION:
    class Solution:
        def numDistinct(self, s: str, t: str) -> int:
            n, m = len(s), len(t)
            if n < m:
                return 0

            dp = [0] * (m + 1)
            dp[0] = 1  # empty t matches any prefix of s

            for ch in s:
                for i in range(m, 0, -1):   # update backwards
                    if t[i-1] == ch:
                        dp[i] += dp[i-1]

            return dp[m]

So the intuition for the flattening comes from:

When filling dp[i][j], we only ever reference:
dp[i][j-1] → current row, previous column
dp[i-1][j-1] → previous row, previous column
the recurrence relation is really \[ dp[i][j] = \underbrace{dp[i][j-1]}_{\text{ignore } s[j-1]} + \underbrace{dp[i-1][j-1]}_{\text{use } s[j-1] \text{ to match } t[i-1]} \]
That means:
Column j depends only on column j-1 in this iteration (row i) and from the previous iteration (row i-1).
We can keep just one row and update it in place if we go backwards in i to avoid overwriting dp[i-1] before it’s used.

Is Subsequence (392)

Interleaving String (97)

We need to look at prefix strings and ask if they can be used to form the prefix string for target. So dp[i][j] asks: “Can I form the prefix of s3 of length i + j using prefixes of s1 and s2 of lengths i and j respectively?” And we build small to big. Space optimisations are obvious when we consider the state transition equation and we realise that we can use a rolling 1D array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
    # M1: 2D DP, no space optimisation
    class Solution:
        def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
            m, n = len(s1), len(s2)
            if (m + n) != len(s3):
                return False

            dp = [[False] * (n + 1) for _ in range(m + 1)]
            dp[0][0] = True

            # init first column (only s1):
            for i in range(1, m + 1):
                dp[i][0] = dp[i - 1][0] and s1[i - 1] == s3[i - 1]

            # init first row (only s2):
            for j in range(1, n + 1):
                dp[0][j] = dp[0][j - 1] and s2[j - 1] == s3[j - 1]

            # fill the rest:
            for i in range(1, m + 1):
                for j in range(1, n + 1):
                    dp[i][j] = (
                        dp[i - 1][j]
                        and s1[i - 1] == s3[i + j - 1]
                    ) or (
                        dp[i][j - 1]
                        and s2[j - 1] == s3[i + j - 1]
                    )

            return dp[m][n]

    # M2: Space optimised, 1D rolling array
    class Solution:
        def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
            m, n = len(s1), len(s2)
            if (m + n) != len(s3):
                return False

            dp = [False] * (n + 1) # in terms of s2
            # trivial fill: nothingness is trivially true
            dp[0] = True

            # trivial fill first row, init first row values:
            # round 1 fill first row
            for j in range(1, n + 1):
                dp[j] = dp[j - 1] and s2[j - 1] == s3[j - 1]

            # for prefixes of s1, this is what we are doing inclusions on
            for i in range(1, m + 1):

                # updates dp[0] for column zero (only s1 to be used as prefix to form s3)
                dp[0] = dp[0] and s1[i - 1] == s3[i - 1]

                for j in range(1, n + 1):
                    dp[j] = (
                            ( # case A: last letter in s1 matches last letter in s3
                                dp[j]
                                and s1[i - 1] == s3[i + j - 1]
                            )
                            or
                            ( # case B: last letter in s2 matches last letter in s3
                                dp[j - 1]
                                and s2[j - 1] == s3[i + j - 1]
                            )
                    )

            return dp[n]

The flattening logic is important to understand:

from v1, we notice that dp[i][j] is caculated as such:
1
2
3
4
5
6
7
                    dp[i][j] = (
                        dp[i - 1][j]  # prev one matched
                        and s1[i - 1] == s3[i + j - 1] # matching char
                    ) or (
                        dp[i][j - 1]  # prev one matched
                        and s2[j - 1] == s3[i + j - 1] # maching char
                    )
So it only depends on:
previous row, same column (we filled top to bottom)
same row, previous column (we fill left to right)
So we can stick to the inner loop being left to right.
Important: When updating dp, iterate over j from left to right (0 to n) because dp[j] corresponds to dp[i][j] and previous state dp[j-1] is still available in this iteration (the current fella).
So in the flattened version:
dp[j] in the inner loop corresponds to dp[i][j] in the 2D version.
Before the inner loop starts, dp[j] holds values from the previous row (i-1).
We update dp[j] using those old values and dp[j-1] (from current row so far).
This update order and rolling over 1D dp ensure the logic is preserved exactly.

Grid DP for Pathfinding and Counting #

Grid traversal, minimum/maximum cost, and counting approaches

Problems #

Unique Paths (62)

This is a classic grid traversal, so the boundaries of the grid give us trivial cases for which we can pre-fill our DP table. The rest of it is just adhering to the rules of traversal that is presented to us. In this case, we just need the number of paths, so we could do the math hack or we could fill thigns in and just take the number of paths. For the DP approach, after we define the naive DP (where dp[i][j] will contain the number of unique ways to get to cell (i, j)), we can observe that the state transition only relies on the cell above and the cell to the left, so we can just keep a 1D array for this and get a whole dimension-optimisation going.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
    # Row-Rolling Space (1D array) optimised DP for 2D DP solution
    class Solution:
        def uniquePaths(self, m: int, n: int) -> int:
            dp = [1] * n  # Initialize for the first row
            for _ in range(1, m):  # For each further row
                for j in range(1, n):
                    dp[j] += dp[j - 1]  # Current cell = left + above (dp[j] is above, dp[j-1] is left)
            return dp[-1]

    # M3: math hack:
    import math

    class Solution:
        def uniquePaths(self, m: int, n: int) -> int:
            return math.comb(m + n - 2, m - 1)

The build up is necessary that’s why we iterate j from left to right direction. Also, the grid can be viewed as a directed acyclic graph (DAG) where each cell points to its right and down neighbors. The number of unique paths is then the count of paths from the top-left node to the bottom-right node. The DP solution is effectively counting paths in this DAG, which confirms the validity of your approach.

The math hack is because \[ \text{Number of Paths} = \binom{m+n-2}{m-1} = \binom{m+n-2}{n-1} \]

Minimum Path Sum (64)

Advanced Grid DP with Obstacles/State #

Variations on grid DP with additional state (obstacles)

Problems #

Interval DP and Range Queries 💪 #

Subarray interval selection/chaining for optimal costs

Problems #

Burst Balloons (312)

This one was wild, probably because I hadn’t seen many interval DP questions prior to this. The rough idea is to think of complements: we try to see what should be the Last Balloon that should be burst within a particular interval. That should help us build up to an answer because then we manage to split the problem into left and right subintervals.

DP setup: dp[i][j] is the max number of coins obtained by bursting the balloons between idx i and j so nums[i + 1] to nums[j + 1], so we get the recurrence that we if we consider k as the best choice for the last to burst balloon, then we get the coins: dp[i][k] + dp[k][j] + (nums[i] * nums[k] * nums[j]) wherein dp[i][k] and dp[k][j] are the left and right subintervals’ answers. The table filling needs to happen from small to large intervals.

Some tricks: edge-padding is useful.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
    class Solution:
        def maxCoins(self, nums: List[int]) -> int:
            # apply a dp solution to count this.
            # insight: we consider contiguous slices using i, j. consider kth balloon as i < k < j so i burst within this rand and k is the LAST to be burst

            # NOTE: we do the edge padding to make life easy: TRICK: sentinel values get used as padding.
            nums = [1] + nums + [1]
            n = len(nums)

            # dp[i][j] is the max number of coins to get if we burst balloons ONLY within i, j range => nums[i + 1] to nums[j + 1]
            dp = [[0] * n for _ in range(n)]
            # answer will be at dp[0][n - 1]

            # trivial fills:
            # 2-fers have no answer because there's no middle, but we don't need to do anything there, it's already 0

            # start table fills. ORder matters, we proxy it using length (which goes from 3 to n)
            for length in range(2, n): # remember this is 0-indexed
                rightmost_idx = n - length - 1

                for left in range(rightmost_idx + 1):
                    right = left + length

                    # now we find ussing ks where k is the last pop index:
                    for k in range(left + 1, right):
                        coins = (
                            dp[left][k] # left interval
​                            + dp[k][right] # right interval
​                            + (nums[left] * nums[right] * nums[k]) # this burst
                        )
                        dp[left][right] = max(dp[left][right], coins) # keep max

            return dp[0][n - 1]

Matrix Chain Multiplication (classic interval DP)

Knapsack Variants (2D and above) #

Multi-resource or multi-choice formations (classic, bounded, unbounded)

we can summarise the family of knapsack problems like so:

Variant	Unlimited Supply?	DP Update Pattern	Example Problem
1. 0/1 Knapsack	Only once	for each `num` in `nums`, for `t` from target to num: `dp[t]	= dp[t-num]`	Subset sum; Partition problem (416)
2. Unbounded Knapsack	Infinite times	for each `num`, for `t` from num to target: `dp[t]	= dp[t-num]`	Coin change infinite supply
3. Bounded Knapsack	Up to limited times	“Decompose” item frequency with binary trick or bounded DP	If each num is present with count
4. Classic Value Knapsack	With values and weights	Use dp table `dp[i][w] = max value`	Standard 0/1/Unbounded knapsack

TODO Problems #

TODO Coin Change II (518) :: 2D in naive implementation

The key idea here is to solve an unbounded variant of the knapsack problem (unbounded because each coin (choice) can be used as many times as desired). The main part of this problem is to realise that it is indeed a 2D or whatever implementation, however, we can easily roll it up into a 1D array, we attempt to use each coin and update the partial sums we can create and in that way each coin can be used as many times as possible. dp[i] is the number of ways to make up that amount = i. Also realise that this a combination counting and we need to absolutely avoid double counting (and caring about permutations) that’s why the outer loop is on coins.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
   class Solution:
       def change(self, amount: int, coins: List[int]) -> int:
           dp = [0] * (amount + 1)

           # trivial base: 1 way to have empty combi
           dp[0] = 1

           # iterates through each coin denomination. This ordering ensures combinations are counted without double counting combinations (because they are permuted differently) (crucial for problems counting combinations).

           for coin in coins:
               # use the same denom as many times as possible:
               for amt in range(coin, amount + 1):
                   dp[amt] += dp[amt - coin]

           return dp[amount]

by the way, this is how we can see the non-flattened 2D approach to connect the dots on how to flatten it into 1D:

2D definition:
dp[i][j] = number of ways to make up amount j using the first i coins (i.e., coins ) (slice)
This is the traditional “table” version before you flatten.
So, base cases:
For any i, dp[i][0] = 1 (There is exactly one way to make amount 0: take nothing.)
For dp[0][j] = 0 when j > 0 (With 0 coins, can’t form any positive amount.)
So our state transitions look like this:
dp[i][j]=dp[i−1][j]+dp[i][j−coins[i−1]] if j≥coins[i−1]
dp[i][j]=dp[i−1][j] if j<coins[i−1]
which gives the following 2D version of the code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
   n = len(coins)
   dp = [[0] * (amount + 1) for _ in range(n + 1)]
   for i in range(n + 1):
       dp[i][0] = 1

   for i in range(1, n + 1):          # using first i coins
       for j in range(amount + 1):     # for each target amount
           if j >= coins[i-1]:
               dp[i][j] = dp[i-1][j] + dp[i][j - coins[i-1]]
           else:
               dp[i][j] = dp[i-1][j]
and our answer would be at dp[n][target]
In the 1D flattening:
We roll up the i dimension (coins) into an update rule by ensuring we process coins one at a time and, for each coin, accumulate number of ways for all amounts in order.
The key is: for each coin, update dp[amt] += dp[amt - coin] iteratively for all amt ≥ coin.
That’s why we get:
1
2
3
4
5
   dp = [0] * (amount + 1)
   dp[0] = 1
   for coin in coins: # this is the "row" progression (when compared to the 2D version)
       for amt in range(coin, amount + 1):
           dp[amt] += dp[amt - coin]
The outer loop on coins is equivalent to the 2D DP’s row progression—each new coin can only build on results found so far, not reorder the combinations.

DP on Trees/Graphs #

DP that uses tree or graph structure where subproblem dependencies are on parent/child/descendants

TODO Problems #

TODO Number of Ways to Paint n × 3 Grid (1411)

Subsequence Matching & Counting with Constraints #

Count number of subsequences/paths in grid/sequence under rules

Problems #

Number of Distinct Subsequences II (940)
Tilings/partitionings (e.g., domino tiling, not covered directly in LC standard set)

Multi-dimensional/Space Reduction DP #

DP with flattening tricks, rolling arrays, or higher dimensions for optimal space

Problems #

Interleaving String (97)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
   # M1: 2D DP, no space optimisation
   class Solution:
       def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
           m, n = len(s1), len(s2)
           if (m + n) != len(s3):
               return False

           dp = [[False] * (n + 1) for _ in range(m + 1)]
           dp[0][0] = True

           # init first column (only s1):
           for i in range(1, m + 1):
               dp[i][0] = dp[i - 1][0] and s1[i - 1] == s3[i - 1]

           # init first row (only s2):
           for j in range(1, n + 1):
               dp[0][j] = dp[0][j - 1] and s2[j - 1] == s3[j - 1]

           # fill the rest:
           for i in range(1, m + 1):
               for j in range(1, n + 1):
                   dp[i][j] = (
                       dp[i - 1][j]
                       and s1[i - 1] == s3[i + j - 1]
                   ) or (
                       dp[i][j - 1]
                       and s2[j - 1] == s3[i + j - 1]
                   )

           return dp[m][n]

   # M2: Space optimised, 1D rolling array
   class Solution:
       def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
           m, n = len(s1), len(s2)
           if (m + n) != len(s3):
               return False

           dp = [False] * (n + 1) # in terms of s2
           # trivial fill: nothingness is trivially true
           dp[0] = True

           # trivial fill first row, init first row values:
           # round 1 fill first row
           for j in range(1, n + 1):
               dp[j] = dp[j - 1] and s2[j - 1] == s3[j - 1]

           # for prefixes of s1, this is what we are doing inclusions on
           for i in range(1, m + 1):

               # updates dp[0] for column zero (only s1 to be used as prefix to form s3)
               dp[0] = dp[0] and s1[i - 1] == s3[i - 1]

               for j in range(1, n + 1):
                   dp[j] = (
                           ( # case A: last letter in s1 matches last letter in s3
                               dp[j]
                               and s1[i - 1] == s3[i + j - 1]
                           )
                           or
                           ( # case B: last letter in s2 matches last letter in s3
                               dp[j - 1]
                               and s2[j - 1] == s3[i + j - 1]
                           )
                   )

           return dp[n]

The flattening logic is important to understand:

from v1, we notice that dp[i][j] is caculated as such:
1
2
3
4
5
6
7
                   dp[i][j] = (
                       dp[i - 1][j]  # prev one matched
                       and s1[i - 1] == s3[i + j - 1] # matching char
                   ) or (
                       dp[i][j - 1]  # prev one matched
                       and s2[j - 1] == s3[i + j - 1] # maching char
                   )
So it only depends on:
previous row, same column (we filled top to bottom)
same row, previous column (we fill left to right)
So we can stick to the inner loop being left to right.
Important: When updating dp, iterate over j from left to right (0 to n) because dp[j] corresponds to dp[i][j] and previous state dp[j-1] is still available in this iteration (the current fella).
So in the flattened version:
dp[j] in the inner loop corresponds to dp[i][j] in the 2D version.
Before the inner loop starts, dp[j] holds values from the previous row (i-1).
We update dp[j] using those old values and dp[j-1] (from current row so far).
This update order and rolling over 1D dp ensure the logic is preserved exactly.

Regular Expression Matching (10) :: rolling row/column

SOE #

Misaligned indices between strings or grids
Incomplete or missing base row/column initialization
When considering questions like FSM-like questions, it’s important to know that not every characteristic will be explicitly stated. Therefore we should think about what rules (explicit and implicit) govern our system.
Consider the following from the “Best Time to Buy and Sell Stock with Cooldown (309)”
careful: the question might give some rules, but there’s a need to outline more than just that
in this case, the third rule is implicit but important for us:
1. You may complete as many transactions as you like (buy one and sell one share multiple times).
2. After you sell a stock, you cannot buy stock on the next day (cooldown one day).
3. You cannot hold more than one stock at a time (must sell before buying again).
Overlaps or double counting in subsequence problems
Subsequence == the relative order of the characters matter even if it’s NOT contiguous.
Subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

Decision Flow #

Comparing sequences? → 2D DP with state (i,j)
String transformation? → Edit distance DP
Grid traversal with constraints? → Grid DP

Style, Tricks and Boilerplate #

Style #

It seems that most of the time, contiguous sequences type questions, we can just attempt to think of prefix-collections of things. We see it here in the case of interleaving strings and a bunch of others as well.

I notice that when we do variable / array rollups for the space optimisations, many a time, to preserve the previous values, we need to do a snapshot. I’ll give some examples:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
  # this is from  problem 309 stock family with cooldown
  class Solution:
      def maxProfit(self, prices: List[int]) -> int:
          if not prices:
              return 0

          n = len(prices)

          # init 3-state dp:
          hold, sold, rest = -prices[0], 0, 0

          for i in range(1, n):
              # snapshot the old vals:
              p_hold, p_sold, p_rest = hold, sold, rest

              hold = max(
                  p_hold, # was holding yesterday also:
                  p_rest - prices[i] # cooldown ytd, can buy today
              )
              sold = p_hold + prices[i] # held until ytd, sold today
              rest = max(
                  p_rest, # rested ytd also
                  p_sold, # sold ytd, rested today
              )

          return max(
              sold, # sold on the last day
              rest # rested on the last day
          )

  # this is from problem 1143 ( longest common subsequence )
  class Solution:
      def longestCommonSubsequence(self, text1: str, text2: str) -> int:
          m, n = len(text1), len(text2)
          dp = [0] * (n + 1)  # dp[j] = LCS length for text1 prefix up to i and text2 prefix up to j

          for i in range(1, m + 1):
              # snapshot
              prev = 0  # This will hold dp[j-1] from previous iteration (the previous diagonal)
              for j in range(1, n + 1):
                  temp = dp[j]  # Save current dp[j] which will become prev in next iteration
                  # case 1: the two are the same characters => both of them should be in
                  if text1[i - 1] == text2[j - 1]:
                      dp[j] = prev + 1
                  # case 2: the two are different, we either include this or exclude this, whichever is better
                  else:
                      dp[j] = max(dp[j], dp[j - 1])
                  prev = temp  # Update prev for next j
          return dp[n]

Remember that for counting problems, we can MOD things without losing information whenever we detect and overflow:

just a note about the module and why it works: it’s because addition and multiplication commute with taking modulo; there’s no loss of information

  The reason you can keep taking modulo at every step (e.g., in `count_end_with_0 = (count_end_with_0 + count_end_with_1) % MOD`) without losing any information is due to a fundamental property of modular arithmetic: **addition and multiplication commute with taking modulo**.[1][2][3]

  ## Why Partial Sums Modulo Work

  For any modulus $$ m $$:

  - $$ (a + b) \bmod m = ((a \bmod m) + (b \bmod m)) \bmod m $$
  - $$ (a \times b) \bmod m = ((a \bmod m) \times (b \bmod m)) \bmod m $$

  This means that no matter how large the intermediate sum or product gets, *as long as you take modulo at each addition or multiplication, the final result modulo $$m$$ will be correct* — you never impact the remainder.[2][1]

  **Intuition:**
  Suppose you are adding up (potentially huge) numbers. All you care about is the remainder (modulo some value). Any excess above multiples of that modulus will always "wrap around" the modulus, so keeping only the current remainder is sufficient.[3][1][2]

  ### Application to Your Code

  The subsequence counting logic may generate astronomical numbers — but storing and updating only the current value modulo $$10^9 + 7$$ is enough, because modulo arithmetic guarantees correctness of the result's remainder. When you sum at the end, as long as each intermediate value was modulo'd, the final sum modulo $$10^9 + 7$$ matches what an exact (but potentially massive) calculation would yield.[1][2][3]

  **No information about the answer modulo $$m$$ is lost by discarding higher-order multiples of $$m$$ at each step.**

  This is what makes modulo arithmetic so robust for "counting" DP methods and combinatorial questions in programming contests and number theory.[2][3][1]

  [1](https://www2.math.upenn.edu/~mlazar/math170/notes06.pdf)
  [2](https://brilliant.org/wiki/modular-arithmetic/)
  [3](https://en.wikipedia.org/wiki/Modular_arithmetic)
  [4](https://www.youtube.com/watch?v=gJtw0c3Lo6E)
  [5](https://www.geeksforgeeks.org/engineering-mathematics/modular-arithmetic/)
  [6](https://davidaltizio.web.illinois.edu/ModularArithmetic.pdf)
  [7](https://calcworkshop.com/number-theory/modular-arithmetic/)
  [8](https://www.math.purdue.edu/~arapura/algebra/algebra8.pdf)
  [9](https://sites.math.rutgers.edu/~zeilberg/essays683/renault.html)