1.1 Khi nào cần 2D state?

1D DP đủ khi state chỉ phụ thuộc vào "ta đang ở đâu" (vị trí i). 2D cần thiết khi state có hai chiều độc lập:

Quy tắc nhận biết

Khi state cần "ghi nhớ" cả vị trí + một chiều khác → 2D. Khi không thể tóm gọn vào 1 số → 2D.

1.2 State Design cho hai chuỗi

Quy ước padding

Bảng dp có kích thước (m+1) × (n+1). Hàng/cột 0 đại diện cho "chuỗi rỗng" — đơn giản hoá base case.

Recurrence chung

if s1[i-1] == s2[j-1]:
    dp[i][j] = dp[i-1][j-1] + something      # ký tự khớp
else:
    dp[i][j] = combine(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

Cụ thể "combine" tuỳ bài: max cho LCS, min cho Edit Distance, add cho Distinct Subsequences.

1.3 DP Table — Trực quan

Hình dung bảng dp giúp viết recurrence nhanh và đúng:

DP table cho LCS("ace", "abc") = 2

Ba mũi tên cốt lõi

• ↖ dp[i-1][j-1]: kết quả khi cả hai chuỗi giảm 1 ký tự cuối.
• ↑ dp[i-1][j]: chỉ s1 giảm 1 ký tự.
• ← dp[i][j-1]: chỉ s2 giảm 1 ký tự.

Recurrence dùng ↖ khi ký tự khớp; dùng ↑/← khi không khớp. Nhìn vào bảng → dễ debug.

1.4 Tối ưu Space — Rolling Array

2D DP tốn O(m × n) space. Khi recurrence chỉ phụ thuộc vào hàng i-1 hoặc cell (i-1, j-1), có thể giảm xuống O(min(m, n)).

Hai biến thể tối ưu

• Hai hàng: giữ hàng i-1 và hàng i, swap qua mỗi vòng. O(2n).
• Một hàng: cập nhật in-place, tận dụng giá trị cũ trước khi ghi đè. O(n) — khó hơn nhưng ít space nhất.

# Two rows version cho LCS
def lcs(s1, s2):
    m, n = len(s1), len(s2)
    if m < n: s1, s2, m, n = s2, s1, n, m    # đảm bảo n nhỏ
    prev = [0] * (n + 1)
    cur = [0] * (n + 1)
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                cur[j] = prev[j-1] + 1
            else:
                cur[j] = max(prev[j], cur[j-1])
        prev, cur = cur, prev
    return prev[n]

Time vẫn O(m × n); Space O(min(m, n)).

2.1 Pattern Two-string DP

Logic chung khi gặp ký tự

if s1[i-1] == s2[j-1]:
    # KHỚP — kế thừa từ dp[i-1][j-1] (cả hai prefix giảm 1)
    dp[i][j] = dp[i-1][j-1] + (1 nếu cần đếm)
else:
    # KHÔNG KHỚP — phải "bỏ" 1 ký tự ở 1 trong 2 bên
    dp[i][j] = combine(dp[i-1][j], dp[i][j-1])
    # combine = max cho LCS, min cho Edit Distance, sum cho count

Bốn bài kinh điển

• Longest Common Subsequence (#1143) — đếm độ dài chuỗi chung dài nhất.
• Edit Distance (#72) — số phép biến đổi tối thiểu.
• Distinct Subsequences (#115) — đếm số cách s1 xuất hiện trong s2.
• Longest Palindromic Subsequence (#516) — LCS giữa s và reverse(s).

2.2 Worked Example 1 — Longest Common Subsequence

Đề (LeetCode #1143): Hai chuỗi text1, text2. Tìm độ dài chuỗi con chung dài nhất (subsequence, không cần liên tiếp).

Ví dụ: "abcde", "ace" → 3 ("ace").

def longestCommonSubsequence(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

Time O(m × n), Space O(m × n) (hoặc O(min(m,n)) với rolling).

Recurrence trực giác

• Khớp ký tự: cả hai chuỗi "tiêu thụ" 1 ký tự → kế thừa dp[i-1][j-1] + 1.
• Không khớp: phải "bỏ" 1 ký tự ở 1 trong 2 chuỗi → max của dp[i-1][j] và dp[i][j-1].

2.3 LCS — DP Table đầy đủ

text1 = "abcde", text2 = "ace". Kỳ vọng: 3.

Các cell bold là điểm "khớp" (text1[i-1] == text2[j-1])

Đáp án ở góc dưới phải = 3.

2.4 Worked Example 2 — Edit Distance (#72)

Đề: Hai chuỗi word1, word2. Tìm số phép biến đổi tối thiểu để biến word1 thành word2. Ba loại phép:

1. Insert: chèn 1 ký tự.
2. Delete: xoá 1 ký tự.
3. Replace: thay 1 ký tự.

Ví dụ: "horse" → "ros" cần 3 phép (rorse → rose → ros).

State

dp[i][j] = số phép tối thiểu để biến word1[0..i-1] thành word2[0..j-1].

Base case

• dp[i][0] = i (xoá i ký tự để rỗng).
• dp[0][j] = j (insert j ký tự).

2.5 Edit Distance — Recurrence chi tiết

Khi word1[i-1] == word2[j-1]: ký tự khớp, không cần biến đổi → dp[i][j] = dp[i-1][j-1].

Khi không khớp, ba lựa chọn:

• Replace: thay word1[i-1] thành word2[j-1] → 1 + dp[i-1][j-1].
• Delete: xoá word1[i-1] → 1 + dp[i-1][j].
• Insert: chèn word2[j-1] vào word1 → 1 + dp[i][j-1].

def minDistance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1): dp[i][0] = i
    for j in range(n + 1): dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
    return dp[m][n]

Time O(m × n).

2.6 Edit Distance — DP Table

word1 = "horse", word2 = "ros". Kỳ vọng: 3.

Đáp án ở góc dưới phải = 3

2.7 Worked Example 3 — Distinct Subsequences (#115)

Đề (Hard): Hai chuỗi s, t. Đếm số cách t xuất hiện trong s dưới dạng subsequence.

Ví dụ: s = "rabbbit", t = "rabbit" → 3 (3 cách chọn các ký tự).

State

dp[i][j] = số cách t[0..j-1] xuất hiện trong s[0..i-1].

Recurrence

Khi s[i-1] == t[j-1]: hai lựa chọn — dùng s[i-1] hoặc bỏ qua nó:

Khi không khớp: phải bỏ qua s[i-1] → dp[i][j] = dp[i-1][j].

def numDistinct(s, t):
    m, n = len(s), len(t)
    if n > m: return 0
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1): dp[i][0] = 1     # 1 cách ghép chuỗi rỗng
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            dp[i][j] = dp[i-1][j]
            if s[i-1] == t[j-1]:
                dp[i][j] += dp[i-1][j-1]
    return dp[m][n]

2.8 Worked Example 4 — Longest Palindromic Subsequence (#516)

Đề: Cho string s. Tìm độ dài subsequence palindrome dài nhất.

Ví dụ: "bbbab" → 4 ("bbbb").

Mẹo: Quy về LCS

Subsequence palindrome của s = subsequence chung của s và reverse(s).

def longestPalindromeSubseq(s):
    return longestCommonSubsequence(s, s[::-1])

Time O(n²).

Approach trực tiếp — Interval DP

State: dp[i][j] = độ dài LPS trong s[i..j]. Đây là Interval DP (xem Phần 5):

def longestPalindromeSubseq(s):
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    for i in range(n): dp[i][i] = 1
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                dp[i][j] = (dp[i+1][j-1] if length > 2 else 0) + 2
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])
    return dp[0][n-1]

Knowledge Check — Two-string DP

3.1 0/1 Knapsack — Pattern

State 2D

dp[i][w] = value max khi xét i items đầu tiên với capacity w.

Recurrence — choose or skip

Take chỉ khả dĩ khi w ≥ w_i. Khi đảo ngược (unbounded), thay dp[i-1][w-w_i] bằng dp[i][w-w_i] để cho phép dùng lại.

Tối ưu space — 1D

Có thể giảm xuống dp[w] bằng cách lặp w từ phải sang trái (đảm bảo dp[w-w_i] vẫn là giá trị "trước khi xét item i"):

for i in range(n):
    for w in range(W, weights[i] - 1, -1):    # ngược lại
        dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

3.2 Worked Example 5 — Partition Equal Subset Sum

Đề (LeetCode #416): Mảng số dương nums. Trả True nếu có thể chia thành 2 subset có tổng bằng nhau.

Quy về 0/1 Knapsack

Tổng = S. Nếu S lẻ → False. Nếu S chẵn → tìm subset có tổng = S/2.

State boolean: dp[w] = True nếu có subset tổng = w.

def canPartition(nums):
    s = sum(nums)
    if s % 2: return False
    target = s // 2
    dp = [False] * (target + 1)
    dp[0] = True
    for num in nums:
        for w in range(target, num - 1, -1):    # 0/1 → ngược
            dp[w] = dp[w] or dp[w - num]
    return dp[target]

Time O(n × target), Space O(target).

3.3 Worked Example 6 — Target Sum

Đề (LeetCode #494): Mảng số dương nums, số target. Đặt + hoặc - trước mỗi số. Đếm số cách để tổng = target.

Quy về 0/1 Knapsack đếm

Đặt P = tập các số có dấu +, N = tập có dấu -. Khi đó:

• P + N = sum(nums) = S
• P - N = target
• → P = (S + target) / 2

Quy về: đếm số cách chọn subset có tổng = (S + target) / 2.

def findTargetSumWays(nums, target):
    s = sum(nums)
    if (s + target) % 2 or s < abs(target): return 0
    new_target = (s + target) // 2
    dp = [0] * (new_target + 1)
    dp[0] = 1
    for num in nums:
        for w in range(new_target, num - 1, -1):
            dp[w] += dp[w - num]
    return dp[new_target]

Time O(n × target), Space O(target).

3.4 0/1 vs Unbounded — So sánh đầy đủ

Quy tắc nhanh để debug

Nếu kết quả vượt kỳ vọng (đếm trùng) → bạn đang vô tình unbounded. Check loop direction.

Nếu kết quả thấp hơn kỳ vọng → bạn đang vô tình 0/1 nhưng bài cho phép unbounded. Đảo loop direction.

Knowledge Check — Knapsack 0/1

4.1 Grid DP — Pattern

Recurrence thường:

Tuỳ bài: tổng (Min Path Sum), đếm cách (Unique Paths), boolean (Dungeon Game).

Khi nào ưu tiên Grid DP?

• Bài đề là grid và yêu cầu đường đi/khoảng cách/tổng.
• Hướng di chuyển hạn chế (chỉ phải/xuống) → DP áp dụng được.
• Hướng tự do (4 hướng) → cần BFS/DFS thay vì DP.

4.2 Worked Example 7 — Unique Paths (#62)

Đề: Lưới m × n. Robot ở (0,0), cần đến (m-1, n-1). Mỗi bước chỉ phải hoặc xuống. Đếm số đường đi.

State

dp[r][c] = số đường từ (0,0) đến (r,c).

Recurrence: đến (r,c) chỉ có thể từ (r-1,c) hoặc (r,c-1):

def uniquePaths(m, n):
    dp = [[1] * n for _ in range(m)]    # hàng/cột 0 đều có 1 cách
    for r in range(1, m):
        for c in range(1, n):
            dp[r][c] = dp[r-1][c] + dp[r][c-1]
    return dp[m-1][n-1]

Time O(m × n), Space O(m × n) hoặc O(n) với rolling.

4.3 Worked Example 8 — Minimum Path Sum (#64)

Đề: Lưới grid[i][j] > 0. Tìm đường từ top-left đến bottom-right có tổng nhỏ nhất. Mỗi bước phải hoặc xuống.

def minPathSum(grid):
    m, n = len(grid), len(grid[0])
    # in-place modification
    for r in range(m):
        for c in range(n):
            if r == 0 and c == 0: continue
            elif r == 0: grid[r][c] += grid[r][c-1]
            elif c == 0: grid[r][c] += grid[r-1][c]
            else: grid[r][c] += min(grid[r-1][c], grid[r][c-1])
    return grid[m-1][n-1]

Time O(m × n), Space O(1) (in-place).

Trace với grid = [[1,3,1],[1,5,1],[4,2,1]]

Đường tối ưu: 1→3→1→1→1 = 7.

5.1 Interval DP — Pattern

Tín hiệu nhận biết

• "Boundary [i, j]", "interval", "kết hợp 2 khoảng".
• "Burst balloons", "matrix chain multiplication".
• "Palindrome questions" thường có thể giải bằng interval DP.

Thứ tự tính

Tính theo chiều dài khoảng tăng dần: dp[i][i] (size 1), dp[i][i+1] (size 2), …

for length in range(1, n + 1):
    for i in range(n - length + 1):
        j = i + length - 1
        # tính dp[i][j] dựa trên dp con (length nhỏ hơn)

Time thường O(n³) (n² cells × n splits).

5.2 Worked Example 9 — Burst Balloons (#312, Hard)

Đề: Mảng nums (giá trị bóng bay). Mỗi lần nổ bóng i được nums[i-1] × nums[i] × nums[i+1] điểm (với biên giả lập = 1). Tìm tổng điểm tối đa khi nổ hết.

Tinh thần "ngược" — Bóng nào nổ CUỐI?

Quan trọng: nghĩ "nổ ngược" — chọn bóng nổ cuối cùng trong khoảng [i, j].

Khi nổ k cuối cùng trong [i, j], hai biên là nums[i-1] và nums[j+1] (đã được "bảo vệ" trong các bài con):

def maxCoins(nums):
    nums = [1] + nums + [1]                # padding biên
    n = len(nums)
    dp = [[0] * n for _ in range(n)]
    for length in range(1, n - 1):
        for i in range(1, n - length):
            j = i + length - 1
            for k in range(i, j + 1):
                dp[i][j] = max(dp[i][j],
                    dp[i][k-1] + dp[k+1][j] + nums[i-1]*nums[k]*nums[j+1])
    return dp[1][n-2]

Time O(n³).

5.3 Burst Balloons — Vì sao "nổ ngược"?

Cách tự nhiên — "nổ xuôi" — nghĩ bóng nào nổ trước. Nhưng có vấn đề:

• Khi nổ bóng đầu tiên k, nó tách [i, j] thành [i, k-1] và [k+1, j]. Nhưng biên của hai khoảng con thay đổi tuỳ vào bóng kế bên.
• Hai khoảng con không độc lập → khó viết recurrence.

Đảo lại — bóng nào nổ CUỐI

Khi k là bóng cuối trong [i, j], lúc đó hai bóng kế là nums[i-1] và nums[j+1] (vì mọi bóng trong [i,j] đã bị nổ).

Hai khoảng con [i, k-1] và [k+1, j] giải độc lập — không "ăn vào" nhau vì k còn nguyên.

5.4 Worked Example 10 — Palindromic Substrings (#647)

Đề: Cho string s. Đếm số substring là palindrome.

Approach Interval DP

dp[i][j] = True nếu s[i..j] là palindrome.

Recurrence: s[i..j] palindrome ⟺ s[i] == s[j] và s[i+1..j-1] palindrome (hoặc length ≤ 2):

def countSubstrings(s):
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    count = 0
    for i in range(n):
        dp[i][i] = True
        count += 1                           # single char palindromes
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                if length == 2 or dp[i+1][j-1]:
                    dp[i][j] = True
                    count += 1
    return count

Time O(n²), Space O(n²).

Knowledge Check — Grid & Interval DP

6.0 Decision Tree — 2D DP

Quy trình code 2D DP

1. Định nghĩa dp[i][j] và padding chuẩn (m+1) × (n+1) cho two-string.
2. Vẽ bảng dp với input nhỏ trên giấy.
3. Viết recurrence dựa trên 3 mũi tên (↖, ↑, ←).
4. Cài tabulation.
5. Tối ưu space (rolling array) nếu cần.

Tổng kết Tuần 13

Đã học

• 2D DP fundamentals: padding (m+1) × (n+1), 3 mũi tên trên bảng dp, rolling array tối ưu space.
• Two-string DP: LCS, Edit Distance (3 phép), Distinct Subsequences (đếm), LPS (quy về LCS với reverse).
• Knapsack 0/1: loop ngược trong 1D — quy tắc "0/1 ngược, Unbounded xuôi"; reduction Target Sum → Subset Sum.
• Grid DP: hướng phải/xuống (DAG); Unique Paths, Min Path Sum.
• Interval DP: dp[i][j] với split point k, time O(n³); Burst Balloons với tinh thần "thao tác ngược".
• Pattern reduction: LPS = LCS(s, reverse(s)); Target Sum → 0/1 Knapsack đếm.

Bài về nhà (12 bài)

1. LeetCode #1143 — Longest Common Subsequence
2. LeetCode #72 — Edit Distance (Hard)
3. LeetCode #115 — Distinct Subsequences (Hard)
4. LeetCode #516 — Longest Palindromic Subsequence
5. LeetCode #416 — Partition Equal Subset Sum
6. LeetCode #494 — Target Sum
7. LeetCode #62 — Unique Paths
8. LeetCode #64 — Minimum Path Sum
9. LeetCode #312 — Burst Balloons (Hard)
10. LeetCode #647 — Palindromic Substrings
11. LeetCode #5 — Longest Palindromic Substring
12. LeetCode #1035 — Uncrossed Lines (LCS variant)