Advanced DP Patterns

1. Introduction

What are Advanced DP Patterns?

Advanced DP Patterns involve multidimensional state mappings that go beyond simple grid routes or 1D arrays:

Edit Distance: Minimizing character edits (insert, delete, replace) to match two strings.

DP on Stocks: Maximizing profits from trading stocks under cooldown or transaction fee constraints.

DP on Trees: Distributing recursive selections on hierarchical nodes (avoiding picking adjacent nodes).

Why study them?

Advanced patterns test your ability to structure complex state machines. For example, stock trading problems require tracking multiple state choices (like buying, selling, or cooldown states) simultaneously per day.

---

2. Mental Models

Edit Distance: Balancing the Scales

Imagine transforming string "horse" to "ros":

You compare letters from right to left.

If characters match, you do nothing.

If they mismatch, you have three tools:

- Insert: Push a character to match. - Delete: Remove a character. - Replace: Rewrite a character.

You recursively choose the path that takes the fewest operations.

DP on Stocks: State Machine Toggle

Imagine a toggle switch representing your portfolio status on day i:

State Hold: You currently own a stock share. Your options today are: continue holding, or sell it.

State Sold / Free: You do not own a share. Your options are: do nothing, or buy a new share.

By tracking these state variables as they transition over time, we calculate optimal transaction yields.

---

3. Core Algorithms & Implementations

1. Edit Distance (LeetCode 72)

State: dp[i][j] = min edits to convert prefix s1[0...i-1] to s2[0...j-1].

Recurrence:

- If s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] - Else: dp[i][j] = 1 + min(dp[i-1][j-1] replace, dp[i-1][j] delete, dp[i][j-1] insert)

2. Best Time to Buy & Sell Stock with Cooldown (LeetCode 309)

State:

- buy[i] = max profit on day i ending with a holding share. - sell[i] = max profit on day i ending with no holding share.

Recurrence:

- buy[i] = max(buy[i-1], sell[i-2] - prices[i]) (since we need 1-day cooldown after selling before buying). - sell[i] = max(sell[i-1], buy[i-1] + prices[i]).

---

4. Visualizing Edit Distance Choices

State branching when converting character A to B:

---

5. Real-World Examples

Natural Language Translation Similarity: Calculating text correlation match scores.

Auto-Trading Portfolio Management: Balancing stock buys, sales, and holding periods under transaction fees to optimize yields.

---

6. Interview Perspective

How Interviewers Ask This Topic

Interviewers test state machine design:

"Given prices, find max profit with transaction fee." -> Same as cooldown. Modify state transition: sell[i] = max(sell[i-1], buy[i-1] + prices[i] - fee).

"Solve House Robber III (Tree DP)." -> Return a size-2 array [robThisNode, skipThisNode] recursively. This solves tree states without needing duplicate memo caches, running in O(N) time.

Common Mistakes

> 2. Wrong Edit Distance Base Cases: Forgetting that converting a string of length L to empty takes L deletions. Thus, dp[i][0] = i and dp[0][j] = j must be set.

---

7. Summary

Edit Distance: 1 + min(replace, delete, insert).

Stocks with Cooldown: Two states: buy (holding) and sell (free). Cooldown references sell[i-2].

Tree DP: Return arrays containing choices recursively to avoid tree memo lookup maps.

---

8. Quiz

Question 1: In Edit Distance, which string operation does the state transition dp[i][j-1] represent?

Answer: Insertion. We match s2[j-1] by inserting it, leaving s1[0...i-1] to be matched with the remaining s2[0...j-2].

Question 2: What is the time complexity of the Edit Distance algorithm?

Answer: O(M × N) time, where M and N are the lengths of the two strings.

Question 3: If prices = [1, 2, 3, 0, 2], what is the maximum profit with 1-day cooldown?

Answer: 3 (Buy at 1, sell at 2, cooldown on 3, buy at 0, sell at 2. Profit = (2-1) + (2-0) = 3).

Question 4: True or False: DP on Trees can be solved without a visited set if the graph is guaranteed to be a tree.

Answer: True. Since trees have no cycles, recursive DFS travels downwards only, so visited sets are not required.

Question 5: Why is Edit Distance O(M * N) space tabulation optimized to O(min(M, N))?

Answer: Because the recurrence dp[i][j] only requires values from the previous row dp[i-1] and the current row, allowing us to drop older matrix rows.