Solving 2D Dynamic Programming Problems

From 1D to 2D Dynamic Programming

The thought process remains the same as for 1D DP:

1. Define the State: What does dp[i][j] represent?
2. Find the Recurrence Relation: How can we compute dp[i][j] from previously solved subproblems (e.g., dp[i-1][j], dp[i][j-1], dp[i-1][j-1])?
3. Identify Base Cases: What are the simplest possible subproblems, usually involving empty inputs?
4. Implement Bottom-Up: Build a 2D table (or grid) to store results, starting from the base cases.

Let's dive into our first problem.

1. Longest Common Subsequence (LCS)

The LCS problem is a classic that forms the basis for many other DP problems, including sequence alignment in bioinformatics, which might resonate with your AI interests.

Problem: Given two strings, text1 and text2, find the length of their longest common subsequence. A subsequence is a new string generated from the original string with zero or more characters deleted, without changing the relative order of the remaining characters.

Example:

• text1 = "abcde"
• text2 = "ace"
• The longest common subsequence is "ace", and its length is 3.

Core Logic and Recurrence Relation

Let's define our state:

• dp[i][j] will be the length of the LCS between the prefix text1[0...i-1] (length i) and text2[0...j-1] (length j).

Now, to compute dp[i][j], we look at the last characters of our current prefixes: text1[i-1] and text2[j-1].

1. Characters Match: If text1[i-1] == text2[j-1], this matching character is part of our LCS. We can add 1 to the length of the LCS of the remaining prefixes, text1[0...i-2] and text2[0...j-2].
   $dp[i][j]=1+dp[i-1][j-1]$

2. Characters Don't Match: If text1[i-1] != text2[j-1], the LCS of the current prefixes must be the same as the LCS of a smaller subproblem. We have two choices:

   • Exclude the character text1[i-1] and find the LCS of text1[0...i-2] and text2[0...j-1]. This is dp[i-1][j].
   • Exclude the character text2[j-1] and find the LCS of text1[0...i-1] and text2[0...j-2]. This is dp[i][j-1].
     We take the best (longest) of these two options.
     $dp[i][j]=\max (dp[i-1][j],dp[i][j-1])$

The following video provides an excellent visual explanation of this logic using a 2D grid.

Bottom-Up Implementation

As shown in the video, we implement this using a 2D array, often called a DP table.

1. Initialization: Create a (m+1) x (n+1) DP table, where m is the length of text1 and n is the length of text2. Initialize it with zeros.
2. Base Cases: The first row and column of the grid will remain 0. This is because the LCS of any string with an empty string is 0. Our initialization already handles this.
3. Iteration: Use nested loops to iterate from i=1 to m and j=1 to n. Inside the loops, apply the recurrence relation we just defined.
4. Result: The final answer is stored in the bottom-right cell of the table, dp[m][n].

The time and space complexity are both O(m * n) because we fill every cell of the m x n grid once.

2. Edit Distance

Edit Distance (also known as Levenshtein Distance) is a classic variation of the LCS pattern. It's a common interview question and has practical applications in areas like spell checkers and computational biology.

Problem: Given two strings, word1 and word2, find the minimum number of operations required to convert word1 to word2. The allowed operations are:

1. Insert a character.
2. Delete a character.
3. Replace a character.

Example:

• word1 = "horse"
• word2 = "ros"
• Operations:
  1. Replace 'h' with 'r' (rorse)
  2. Delete 'r' (rose)
  3. Delete 'e' (ros)
• Minimum operations: 3.

Core Logic and Recurrence Relation

This problem fits the same 2D DP template.

• State: dp[i][j] will be the minimum number of operations to convert word1[0...i-1] to word2[0...j-1].

Again, we compare word1[i-1] and word2[j-1]:

1. Characters Match: If word1[i-1] == word2[j-1], no operation is needed for this character. The cost is simply the cost of converting the prefixes without these characters.
   $dp[i][j]=dp[i-1][j-1]$

2. Characters Don't Match: If word1[i-1] != word2[j-1], we must perform one operation. We choose the one that results in the minimum total cost:

   • Insert: We want to make word1[0...i-1] match word2[0...j-1]. This is equivalent to matching word1[0...i-1] to word2[0...j-2] and then inserting the character word2[j-1]. The cost is 1 + dp[i][j-1].
   • Delete: We can match word1[0...i-2] to word2[0...j-1] and then delete the character word1[i-1]. The cost is 1 + dp[i-1][j].
   • Replace: We can match word1[0...i-2] to word2[0...j-2] and then replace word1[i-1] with word2[j-1]. The cost is 1 + dp[i-1][j-1].
     We take the minimum of these three choices.
     $dp[i][j]=1+\min (dp[i-1][j],dp[i][j-1],dp[i-1][j-1])$

The following video and article explain this logic in detail.

To reinforce this, the following article provides a superb, step-by-step walkthrough of filling the DP table.

Bottom-Up Implementation

The implementation is very similar to LCS, but with different base cases and a different recurrence for the non-matching case.

1. Initialization: Create a (m+1) x (n+1) DP table.
2. Base Cases:
   • dp[0][j] = j: To convert an empty string to a string of length j, you need j insertions.
   • dp[i][0] = i: To convert a string of length i to an empty string, you need i deletions.
3. Iteration: Use nested loops from i=1 to m and j=1 to n, applying the Edit Distance recurrence.
4. Result: The answer is dp[m][n].

Like LCS, the time and space complexity are O(m * n).

Conclusion

In this lesson, we transitioned from 1D to 2D dynamic programming and solved two cornerstone problems in this category. You've seen how a single pattern can be adapted to solve different, but related, problems.

Key Takeaways:

• 2D DP Pattern: For problems comparing two sequences of length m and n, the state is typically dp[i][j] and the solution is built in an O(m * n) table.
• LCS Recurrence:
  • If s1[i-1] == s2[j-1]: dp[i][j] = 1 + dp[i-1][j-1]
  • If s1[i-1] != s2[j-1]: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
• Edit Distance Recurrence:
  • If word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1]
  • If word1[i-1] != word2[j-1]: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
• Base Cases are Key: Pay close attention to the base cases. For LCS, it was all zeros. For Edit Distance, it was the cost of insertions/deletions against an empty string (i and j).

In our next lesson, we will continue our exploration of dynamic programming by tackling knapsack-style problems. These problems introduce a new constraint (like weight or capacity) and will require a slightly different, but equally powerful, way of defining our DP state.