Advanced Dynamic Programming

# CHAPTER 14

Advanced Dynamic Programming #

1. Chapter Introduction #

2. Pattern 1: 2D Grid Pathfinding #

*1. Define the State:* The robot's position is defined by two variables: row and col. *2. State Transition:* How does the robot get to a specific square? It must have arrived from the square directly ABOVE it, or the square directly to the LEFT of it. *Equation:* dp[row][col] = dp[row - 1][col] + dp[row][col - 1] *3. Base Cases:* The first row and the first column all have exactly 1 unique path to them (moving purely straight).

def uniquePaths(m, n):
    # Initialize an M x N matrix with 1s
    dp = [[1] * n for _ in range(m)]
    
    # Iterate through the grid, skipping row 0 and col 0
    for row in range(1, m):
        for col in range(1, n):
            # Paths = Paths from Above + Paths from Left
            dp[row][col] = dp[row - 1][col] + dp[row][col - 1]
            
    return dp[m - 1][n - 1] # Bottom-right corner
# Time: O(M * N), Space: O(M * N)

3. Pattern 2: Longest Common Subsequence (LCS) #

*The 2D Matrix Setup:* Create a 2D matrix where the rows represent characters of text1 and the columns represent characters of text2. *State Transition Logic:*

• If text1[i] == text2[j]: The characters match! The sequence length increases by 1 over the sequence length *before* these characters. dp[i][j] = 1 + dp[i-1][j-1] (Diagonal movement).

• If they do NOT match: We must choose the best previous sequence by either ignoring text1[i] or ignoring text2[j]. dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (Max of cell Above or cell to the Left).

4. Pattern 3: The 0/1 Knapsack Problem #

*State Variables:* We need a 2D array: dp[item_index][current_capacity]. *State Transition Logic:* At any given item, we have two choices:

1. 1. Exclude it: The value is whatever the max value was for the previous items at this exact capacity. dp[i-1][capacity]

1. 2. Include it: We add the item's value, PLUS the max value we previously found for the *remaining* weight capacity. val[i] + dp[i-1][capacity - weight[i]]

5. String Manipulation: Edit Distance #

• If characters match: dp[i][j] = dp[i-1][j-1] (Cost is 0, inherit previous state).

• If characters differ: Take the min() of Insert, Delete, or Replace operations, and add 1 to the cost.

6. Real-World Scenario: Diff Tools #

7. Mini Project: 2D Space Optimization #

8. Common Mistakes #

• 2D Array Initialization in Python: A fatal python trap: dp = [[0] * n] * m. This creates m references to the *exact same* single row. Modifying dp[0][0] will miraculously change dp[1][0] and dp[2][0]. You MUST initialize using list comprehension: dp = [[0] * n for _ in range(m)].

• Index Out of Bounds: When checking dp[i-1][j], if i is 0, the program will crash. Always pad your DP tables with an extra row of zeros (size + 1) to act as safe base cases.

9. Best Practices #

• Draw the Grid: In an interview, do not try to hold a 2D state transition in your head. Physically draw a 4x4 matrix on the whiteboard. Fill in the base cases. Then, manually fill in the first empty cell using your logic.

10. Exercises #

1. 1. In the 0/1 Knapsack problem, why do we need a 2D array instead of a 1D array?

1. 2. Draw a 3x3 DP table for the Unique Paths problem. Manually calculate the value of the bottom-right cell.

11. MCQs #

14. Interview Questions #

• Q: "Given an m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path. You can only move down or right." (LeetCode 64).

15. FAQs #

• Q: 2D DP is too hard for me to hold in my head. What do I do?

16. Summary #

17. Next Chapter Recommendation #