Solving 2D Dynamic Programming Problems

Hello! Welcome to your next lesson in the "Advanced Algorithmic Patterns" module.

In our previous lesson, we established a solid foundation in 1D Dynamic Programming. You learned how to take a problem with optimal substructure and overlapping subproblems, formulate a recurrence relation, and implement it using both top-down memoization and bottom-up tabulation. We also analyzed the critical trade-offs between these two approaches, especially concerning memory safety and performance—a key consideration in production environments like the ones you build at AWS.

Today, we'll extend those concepts to two dimensions. Our goal is to solve a classic 2D dynamic programming problem, analyzing the time and space complexity of the solution. We'll see that while the state becomes a 2D grid instead of a 1D array, the core principles of DP remain exactly the same. We'll focus on the Longest Common Subsequence (LCS) problem, a pattern that forms the basis for many other string and sequence-related problems.

---

1. From 1D to 2D Dynamic Programming

In 1D DP, the state of a subproblem could be defined by a single variable, like dp[i] for the number of ways to climb i stairs. In 2D DP, the state is defined by two variables, typically representing indices into two different inputs. This naturally maps to a 2D table or grid where dp[i][j] stores the solution to a subproblem involving the first i elements of one input and the first j elements of another.

Let's explore this with the quintessential 2D DP problem: Longest Common Subsequence.

2. The Longest Common Subsequence (LCS) Problem

First, let's clearly define the problem.

To summarize:

• A subsequence is formed by deleting zero or more characters from a string while maintaining the relative order of the remaining characters. "ace" is a subsequence of "abcde".
• A common subsequence is a sequence that is a subsequence of two different strings.
• The Longest Common Subsequence is the common subsequence with the maximum possible length.

A brute-force approach would involve generating all subsequences for both strings (an exponential operation, $O(2^n)$) and then comparing them. This is computationally infeasible for all but the smallest strings, signaling that a more efficient approach like DP is needed.

3. Formulating the Recurrence Relation

The key to any DP problem is defining the state and the recurrence. For LCS, our state will be lcs(i, j), representing the length of the longest common subsequence between the prefixes text1[0...i] and text2[0...j].

To compute lcs(i, j), we only need to look at the characters text1[i] and text2[j].

• Case 1: The characters match (text1[i] == text2[j])
  If the characters match, they contribute to the LCS. We can add 1 to our count and find the LCS of the remaining smaller strings: text1[0...i-1] and text2[0...j-1].
  $\text{lcs}(i,j)=1+\text{lcs}(i-1,j-1)$

• Case 2: The characters do not match (text1[i] != text2[j])
  If they don't match, we can't include both. We must discard one of them and take the best result possible from the remaining subproblems. We have two choices:

  1. Discard text1[i] and find the LCS of text1[0...i-1] and text2[0...j].
  2. Discard text2[j] and find the LCS of text1[0...i] and text2[0...j-1].
     We take the maximum of these two possibilities.
     $\text{lcs}(i,j)=\max (\text{lcs}(i-1,j),\text{lcs}(i,j-1))$

The video below gives an excellent, detailed walkthrough of this logic.

Once we have the recurrence, we can visualize the DP table. Each cell dp[i][j] will be filled based on the values in adjacent cells, as dictated by the recurrence.

4. Implementation Strategies

Just like with 1D DP, we can implement our solution using memoization or tabulation.

Top-Down (Memoization)

This approach is a direct translation of our recursive formula, augmented with a 2D cache to store results of (i, j) pairs we've already computed.

Here's a Python implementation. The structure is identical to the 1D case, but the cache and function parameters are now 2D.

# LeetCode 1143: Longest Common Subsequence (Top-Down)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:



        # Cache for memoization. Key is a tuple (i, j).
        memo = {}
        
        def solve(i, j):



            # Base case: if either string is exhausted, there's no common subsequence.
            if i < 0 or j < 0:
                return 0
            



            # Check cache
            if (i, j) in memo:
                return memo[(i, j)]




            # Case 1: Characters match
            if text1[i] == text2[j]:
                result = 1 + solve(i - 1, j - 1)



            # Case 2: Characters do not match
            else:
                result = max(solve(i - 1, j), solve(i, j - 1))
            



            # Store result in cache
            memo[(i, j)] = result
            return result

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

• Time Complexity: $O(m\times n)$. Each state (i, j) is computed exactly once.
• Space Complexity: $O(m\times n)$ for the memoization cache. Additionally, there's a recursive stack space cost of $O(m+n)$ in the worst case.

Bottom-Up (Tabulation)

This iterative approach eliminates recursion by building a 2D DP table from the ground up. This avoids the risk of stack overflow for large inputs.

A common and robust technique for tabulation in string DP problems is to shift the indices. We create a DP table of size (m+1) x (n+1). Here, dp[i][j] will represent the LCS length for text1 of length i (i.e., text1[0...i-1]) and text2 of length j (text2[0...j-1]). This 1-based indexing for the DP table makes handling the base cases (empty strings) clean—the 0-th row and 0-th column are naturally initialized to 0.

The video you watched covers this index-shifting technique very well. Let's see it in code.

Here is a Python implementation using this bottom-up, index-shifted approach:

# LeetCode 1143: Longest Common Subsequence (Bottom-Up)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)



        # dp[i][j] stores LCS of text1[:i] and text2[:j]
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        for i in range(1, m + 1):
            for j in range(1, n + 1):



                # Characters in strings are at i-1 and j-1
                if text1[i - 1] == text2[j - 1]:
                    dp[i][j] = 1 + dp[i - 1][j - 1]
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        
        return dp[m][n]

• Time Complexity: $O(m\times n)$ due to the nested loops.
• Space Complexity: $O(m\times n)$ for the 2D DP table.

5. Space Optimization

As an SDE II, you're always looking for ways to optimize. Notice that to compute dp[i][j], we only ever need values from the previous row (i-1) and the current row (i). We don't need the entire m x n table in memory at once.

This allows us to optimize the space complexity from $O(m\times n)$ down to $O(n)$ (or $O(\min (m,n))$ by iterating over the shorter string). We only need to keep track of the "previous" and "current" rows.

This optimization is a standard move in DP interviews and demonstrates a deeper understanding of the algorithm's dependencies.

---

6. Another Classic: Edit Distance

The LCS pattern is highly versatile. A closely related problem is Edit Distance (also known as Levenshtein Distance). The goal is to find the minimum number of single-character insertions, deletions, or substitutions required to change one string into another.

The recurrence is similar but accounts for the cost of each operation:

• If text1[i] == text2[j]: cost = 0, so dp[i][j] = dp[i-1][j-1].
• If text1[i] != text2[j]: cost = 1, so we take the minimum of the three possible operations: \underbrace{dp[i-1][j]}_{\text{delete}}, \underbrace{dp[i][j-1]}_{\text{insert}}, \underbrace{dp[i-1][j-1]}_{\text{replace}} ) $$

Given your expertise in Rust, it's valuable to see how these concepts are implemented in a performance-oriented, type-safe language.

---

Conclusion

You have now successfully transitioned from 1D to 2D dynamic programming. The problems are more complex, but the underlying methodology remains a powerful and consistent tool.

Key Takeaways:

• 2D DP State: The state of a subproblem is typically defined by two parameters, (i, j), which map to a 2D grid.
• Recurrence is Key: The core of the solution lies in defining how dp[i][j] relates to its neighbors (e.g., dp[i-1][j], dp[i][j-1], dp[i-1][j-1]).
• LCS & Edit Distance: These are foundational 2D DP problems. Mastering their patterns will help you solve many variations.
• Implementation & Optimization: Both memoization and tabulation are valid strategies, with tabulation being safer for large inputs. Space optimization from $O(m\times n)$ to $O(n)$ is a crucial technique to know.

Next Lesson Preview

In the next lesson, we will switch gears to a completely different algorithmic paradigm: Binary Search on the Answer Space. You're familiar with binary searching a sorted array, but we'll explore how to apply the same principle to find an optimal value within a monotonic range of possible solutions—a powerful technique for certain optimization problems that don't fit the DP model.