Chương 29 - Dynamic Programming

Dynamic Programming (DP) = đệ quy + memoization (hoặc bottom-up). Cần 2 tính chất: optimal substructure (lời giải tối ưu của bài lớn xây từ lời giải tối ưu của bài con) + overlapping subproblems (bài con bị lặp). Chương lớn nhất sách - 18 bài chia 3 nhóm:

  • DP I (29.1–29.6): LCS, LIS, Edit Distance, Knapsack
    • DP 2D kinh điển.
  • DP II (29.7–29.12): Coin Change, Stock Trading, House Robber - DP trên trục thời gian.
  • DP III (29.13–29.18): Partition / Interval DP - DP trên đoạn.

Mục tiêu chương

Sau chương này, bạn sẽ:

  • Thuộc 4 sub-pattern: sequence DP, knapsack, interval DP, partition DP.
  • Mỗi bài DP có 5 yếu tố: state, transition, base, answer, duyệt order.
  • Phân biệt top-down (@cache) vs bottom-up (table).
  • Optimize space: rolling 1D khi transition chỉ dùng row trước.

Taxonomy 4 nhóm DP trong chương này

Chương dài nhất sách. Để không lạc, mỗi bài rơi vào 1 trong 4 nhóm:

Nhóm Bài (LC) Đặc điểm chung
DP I - Sequence DP (2D) 29.1 LCS, 29.2 LIS, 29.3 Edit Distance State = (i, j) đại diện 2 prefix
DP I - Knapsack 29.4 0/1 Knapsack, 29.5 Partition Equal Sum, 29.6 Russian Doll State = (i, capacity)
DP II - Linear DP 29.7 Coin Change, 29.8 Coin Change II, 29.9 Stock Cooldown, 29.10 Stock IV, 29.11 House Robber II, 29.12 Max Product State = dp[i] hoặc dp[i][k]
DP III - Interval / Partition DP 29.13 Palindrome Partition II, 29.14 Burst Balloons, 29.15 MCM, 29.16 Cut Stick, 29.17 Stone Game VII, 29.18 Strange Printer State = dp[l][r], split tại k

Bảng state/transition cho mỗi bài

Khi gặp 1 bài DP, 4 câu hỏi cốt lõi: (1) State là gì? (2) Transition thế nào? (3) Base case? (4) Đáp án ở đâu?

Bài State Transition Base Answer
29.1 LCS dp[i][j] = LCS của s1[..i], s2[..j] Match: dp[i-1][j-1]+1; Else: max(dp[i-1][j], dp[i][j-1]) dp[0][j] = dp[i][0] = 0 dp[m][n]
29.2 LIS tails[k] = giá trị nhỏ nhất kết LIS dài k+1 bisect_left + replace/append tails = [] len(tails)
29.3 Edit Distance dp[i][j] = min edit s1[..i] → s2[..j] Match: dp[i-1][j-1]; Else: 1 + min(3 chiều) dp[i][0]=i, dp[0][j]=j dp[m][n]
29.4 0/1 Knapsack dp[w] = max value với capacity w dp[w] = max(dp[w], dp[w-wi]+vi) (duyệt ngược) dp[0..W] = 0 dp[W]
29.5 Partition Equal Sum dp[w] = có subset sum = w? dp[w] = dp[w] or dp[w-x] dp[0] = True dp[sum/2]
29.6 Russian Doll Sort 2D + LIS trên h Như LIS (29.2) - len(tails)
29.7 Coin Change dp[a] = min coin tổng a dp[a] = min(dp[a-c]+1) dp[0] = 0 dp[amount]
29.8 Coin Change II dp[a] = số cách dp[a] += dp[a-c] (outer coin) dp[0] = 1 dp[amount]
29.9 Stock Cooldown hold[i], sold[i], rest[i] 3 transitions giữa state hold[0] = -prices[0] max(sold[-1], rest[-1])
29.10 Stock IV dp[t][i] = max profit ≤ t txn đến ngày i max(dp[t][i-1], price[i]+max_diff) dp[0][i] = 0 dp[k][n-1]
29.11 House Robber II Tách 2 case (rob 0 / không) Như Robber I - max(case_1, case_2)
29.12 Max Product cur_max, cur_min rolling Swap khi x < 0 Start = nums[0] max(best)
29.13 Palindrome Partition II dp[i] = min cut cho s[..i] dp[i] = min(dp[j-1]+1) nếu s[j..i] palindrome dp[i]=0 nếu s[0..i] palindrome dp[n-1]
29.14 Burst Balloons dp[i][j] = max điểm nổ (i, j) exclusive max(arr[i]*arr[k]*arr[j] + dp[i][k] + dp[k][j]) dp[i][i+1] = 0 dp[0][n-1]
29.15 MCM dp[i][j] = min phép nhân Ai..Aj min(dp[i][k]+dp[k+1][j]+p[i-1]*p[k]*p[j]) dp[i][i]=0 dp[1][n]
29.16 Cut Stick dp[i][j] = min cost cuts (cuts[i], cuts[j]) min(dp[i][k]+dp[k][j]) + cuts[j]-cuts[i] dp[i][i+1]=0 dp[0][m-1]
29.17 Stone Game VII dp[l][r] = max diff người hiện tại max(sum-stones[l] - dp[l+1][r], sum-stones[r] - dp[l][r-1]) dp[i][i]=0 dp[0][n-1]
29.18 Strange Printer dp[i][j] = min turn in s[i..j] min(dp[i][j-1]+1, dp[i][k] + dp[k+1][j-1] khi s[k]==s[j]) dp[i][i]=1 dp[0][n-1]

Roadmap đọc 18 bài

Nếu chỉ có 1 ngày, đọc theo thứ tự ưu tiên:

  1. Foundations (must): 29.1 LCS, 29.2 LIS, 29.7 Coin Change - gateway cho mọi DP khác.
  2. Stock family (rất hay hỏi): 29.9 Stock Cooldown, 29.10 Stock IV.
  3. Knapsack (LC tag siêu phổ biến): 29.4 0/1, 29.5 Partition.
  4. Interval DP (thường Hard): 29.14 Burst Balloons → 29.13 Palindrome Partition II.
  5. Còn lại: skip nếu thiếu thời gian.

Khi nào dùng pattern này?

  • Bài yêu cầu max/min/count với cấu trúc đệ quy.
  • Có state rõ ràng và transition đơn giản.
  • Brute force exponential, nhưng số subproblem polynomial.

3 bước xây DP: 1. Định nghĩa state: dp[i][j] = ? 2. Transition: dp[i][j] = f(dp[i-1][j], dp[i][j-1], ...) 3. Base case + thứ tự duyệt: từ nhỏ đến lớn.

Top-down (memo) vs Bottom-up (tabulation): - Top-down: viết đệ quy + @cache. Dễ thấy “transition”. - Bottom-up: vòng for tăng dần. Tiết kiệm stack, dễ tối ưu space.

Template code 

from functools import cache

# 1) Top-down
@cache
def dp(*state):
    if base_condition(*state):
        return base_value
    return combine([dp(*sub_state) for sub_state in transitions(*state)])


# 2) Bottom-up 2D
dp = [[0] * cols for _ in range(rows)]
for i in range(rows):
    for j in range(cols):
        if base(i, j):
            dp[i][j] = base_value
        else:
            dp[i][j] = f(dp[i-1][j], dp[i][j-1], ...)
return dp[-1][-1]


# 3) Space-optimized 1D (khi transition chỉ dùng dòng trước)
prev = [0] * cols
for i in range(rows):
    cur = [0] * cols
    for j in range(cols):
        cur[j] = f(prev[j], cur[j-1], ...)
    prev = cur

Bài tự luyện cuối chương

  • LC 198 - House Robber
  • LC 64 - Minimum Path Sum
  • LC 91 - Decode Ways
  • LC 583 - Delete Operation for Two Strings
  • LC 712 - Minimum ASCII Delete Sum
  • LC 887 - Super Egg Drop

DP I - DP 2D kinh điển (LCS, LIS, Knapsack)

29.1 Longest Common Subsequence (LC 1143)

Đề bài

Cho 2 chuỗi s1, s2. Tìm độ dài LCS (longest common subsequence).

Ví dụ 

Input:  text1 = "abcde", text2 = "ace"
Output: 3
        (LCS dài nhất là "ace")

Input:  text1 = "abc", text2 = "def"
Output: 0
        (không có ký tự chung)

Ràng buộc

  • 1 <= len(text1), len(text2) <= 1000

Clarifying questions

  • String rỗng? → LCS = 0.
  • Case-sensitive? → Theo đề: có.

Hướng tiếp cận

dp[i][j] = LCS của s1[0..i-1] và s2[0..j-1].

  • Nếu s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] + 1.
  • Ngược lại: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

Code Python 3 

class Solution:
    def longestCommonSubsequence(self, s1: str, s2: str) -> int:
        m, n = len(s1), len(s2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if s1[i - 1] == s2[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]

Phân tích độ phức tạp

  • Thời gian: O(m · n).
  • Bộ nhớ: O(m · n); có thể giảm về O(min(m, n)).

Bình luận

  • Space O(min(m,n)): chỉ giữ 2 row.

Bài tự luyện liên quan

  • LC 1035 - Uncrossed Lines (tương đương LCS).
  • LC 583 - Delete Operation for Two Strings.

29.2 Longest Increasing Subsequence (LC 300) - O(n log n)

Đề bài

Tìm độ dài LIS (strictly increasing) của nums.

Ví dụ 

Input:  nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
        (1 LIS dài nhất: [2, 3, 7, 18]; có thể có nhiều LIS khác)

Input:  nums = [0, 1, 0, 3, 2, 3]
Output: 4
        (1 LIS dài nhất: [0, 1, 2, 3])

Ràng buộc

  • 1 <= len(nums) <= 2500
  • -10^4 <= nums[i] <= 10^4

Clarifying questions

  • Mảng rỗng? → Trả 0.
  • Strict increasing? → Có (< không ≤).

Hướng tiếp cận

DP O(n²) - dp[i] = max(dp[j]) + 1 với j < i, nums[j] < nums[i].

O(n log n) - Patience Sort: - tails[i] = giá trị nhỏ nhất kết thúc LIS độ dài i + 1. - Duyệt nums, dùng binary search (bisect_left) để tìm vị trí thay/extend.

Code Python 3 

from bisect import bisect_left
from typing import List

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        tails: list[int] = []
        for x in nums:
            i = bisect_left(tails, x)
            if i == len(tails):
                tails.append(x)
            else:
                tails[i] = x
        return len(tails)

Phân tích độ phức tạp

  • Thời gian: O(n log n).
  • Bộ nhớ: O(n).

Bình luận

  • tails không phải LIS thật - chỉ length đúng.
  • Tái xuất ở Chương 38, 39 với binary search + DP.

Bài tự luyện liên quan

  • LC 354 - Russian Doll Envelopes (bài 29.6).
  • LC 673 - Number of LIS.

29.3 Edit Distance (LC 72)

Đề bài

Cho word1, word2. Số phép biến đổi tối thiểu (insert, delete, replace) để word1 → word2.

Ví dụ 

Input:  word1="horse", word2="ros"
Output: 3
Giải thích: horse → rorse → rose → ros (3 thao tác)

Ràng buộc

  • 0 <= len(word1), len(word2) <= 500

Clarifying questions

  • String rỗng? → Distance = độ dài cái còn lại.
  • Có thao tác khác (swap)? → Không, chỉ insert/delete/replace.

Hướng tiếp cận

dp[i][j] = edit distance giữa prefix i của word1 và prefix j của word2.

  • word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1].
  • Ngược lại: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) (delete, insert, replace).

Code Python 3 

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        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], dp[i][j - 1], dp[i - 1][j - 1])
        return dp[m][n]

Phân tích độ phức tạp

  • Thời gian: O(m · n).
  • Bộ nhớ: O(m · n); có thể giảm về O(min(m, n)).

Bình luận

  • Bẫy: off-by-one ở base case: dp[i][0] = i, dp[0][j] = j.
  • Follow-up: LC 583 chỉ insert/delete (không replace).

Bài tự luyện liên quan

  • LC 583 - Delete Operation for Two Strings.
  • LC 712 - Minimum ASCII Delete Sum.

29.4 0/1 Knapsack (bài kinh điển)

Đề bài

Cho n đồ vật, mỗi cái có weight[i] và value[i]. Túi có sức chứa W. Chọn các đồ vật để max tổng value, mỗi cái dùng ≤ 1 lần.

Ví dụ 

Input:  weights=[1,3,4,5], values=[1,4,5,7], W=7
Output: 9

Ràng buộc

  • 1 <= n <= 100
  • 1 <= W <= 1000

Clarifying questions

  • weights[i] = 0? → Có; pickup free.
  • n = 0? → Trả 0.

Hướng tiếp cận

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

dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i-1]] + value[i-1]) (nếu fit).

Code Python 3 

from typing import List

def knapsack_01(weights: List[int], values: List[int], W: int) -> int:
    n = len(weights)
    dp = [0] * (W + 1)
    for i in range(n):
        # Duyệt ngược để mỗi item dùng ≤ 1 lần.
        for w in range(W, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[W]

Phân tích độ phức tạp

  • Thời gian: O(n · W).
  • Bộ nhớ: O(W) sau khi rolling array.

Bình luận

  • 1D rolling array với duyệt ngược là trick chuẩn.
  • Unbounded knapsack (dùng nhiều lần): duyệt xuôi thay vì ngược.

Bài tự luyện liên quan

  • LC 416 - Partition Equal Subset Sum (bài 29.5).

29.5 Partition Equal Subset Sum (LC 416)

Đề bài

Cho nums (positive). Kiểm tra có thể chia làm 2 tập có tổng bằng nhau không.

Ví dụ 

Input:  nums = [1, 5, 11, 5]
Output: True
(chia được thành [1,5,5] và [11], 2 nhóm tổng = 11)

Ràng buộc

  • 1 <= len(nums) <= 200
  • 1 <= nums[i] <= 100

Clarifying questions

  • Sum lẻ? → Trả False sớm.
  • n = 1? → Không thể chia thành 2 → False.

Hướng tiếp cận

Đặt S = sum(nums). Nếu S lẻ → False. Tìm subset có tổng S / 2 → knapsack boolean DP.

dp[w] = True/False (có subset tổng = w không).

Code Python 3 

from typing import List

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2: return False
        target = total // 2
        dp = [False] * (target + 1)
        dp[0] = True
        for x in nums:
            for w in range(target, x - 1, -1):
                dp[w] = dp[w] or dp[w - x]
        return dp[target]

Phân tích độ phức tạp

  • Thời gian: O(n · sum/2).
  • Bộ nhớ: O(sum/2).

Bình luận

  • Bẫy: quên check sum lẻ → return False sớm tiết kiệm tính toán.
  • Follow-up: LC 698 (Partition K Subsets) - Bitmask DP, Chương 40.1.

Bài tự luyện liên quan

  • LC 494 - Target Sum.
  • LC 698 - Partition to K Equal Sum Subsets (Chương 40).

29.6 Russian Doll Envelopes (LC 354)

Đề bài

Cho envelopes[i] = [w, h]. Envelope A fit trong B nếu A.w < B.w và A.h < B.h. Tìm độ dài chuỗi fit tối đa.

Ví dụ 

Input:  envelopes = [[5,4], [6,4], [6,7], [2,3]]
        (mỗi phần tử [width, height])
Output: 3   (chuỗi [2,3] ⊂ [5,4] ⊂ [6,7])

Ràng buộc

  • 1 <= len(envelopes) <= 10^5
  • 1 <= w_i, h_i <= 10^5

Clarifying questions

  • Có envelope trùng (cùng w, h)? → Không fit lẫn nhau (strict).

Hướng tiếp cận

Trick “sort 2D”: sort theo w tăng, h giảm với cùng w (để tránh 2 envelope cùng w fit lẫn nhau). Sau đó tìm LIS trên dãy h.

Code Python 3 

from bisect import bisect_left
from typing import List

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        envelopes.sort(key=lambda e: (e[0], -e[1]))
        tails: list[int] = []
        for _, h in envelopes:
            i = bisect_left(tails, h)
            if i == len(tails):
                tails.append(h)
            else:
                tails[i] = h
        return len(tails)

Phân tích độ phức tạp

  • Thời gian: O(n log n).
  • Bộ nhớ: O(n).

Bình luận

  • Trick -e[1]: với cùng w, h giảm → cùng w không tạo “LIS” trên h.
  • Cùng pattern ở LC 1691 (Max Height Stacking Cuboids
    • Chương 39).

Bài tự luyện liên quan

  • LC 300 - LIS.
  • LC 1691 - Stacking Cuboids.

DP II - Coin Change & Stock Trading

29.7 Coin Change (LC 322)

Đề bài

Cho coin denominations và amount. Số coin tối thiểu để gộp thành amount. -1 nếu không thể.

Ví dụ 

Input:  coins=[1,2,5], amount=11
Output: 3
Giải thích: 11 = 5+5+1

Ràng buộc

  • 1 <= len(coins) <= 12
  • 1 <= coins[i] <= 2^31-1
  • 0 <= amount <= 10^4

Clarifying questions

  • amount = 0? → Trả 0.
  • Không thể tạo? → Trả -1.

Hướng tiếp cận

dp[a] = min coin để gộp thành a. dp[0] = 0. dp[a] = min(dp[a - c] + 1 for c in coins if c <= a).

Code Python 3 

from typing import List

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        INF = amount + 1
        dp = [0] + [INF] * amount
        for a in range(1, amount + 1):
            for c in coins:
                if c <= a:
                    dp[a] = min(dp[a], dp[a - c] + 1)
        return -1 if dp[amount] > amount else dp[amount]

Phân tích độ phức tạp

  • Thời gian: O(amount · n_coins).
  • Bộ nhớ: O(amount).

Bình luận

  • Bẫy: không phân biệt được “không thể tạo” (INF) và đáp án hợp lệ → dùng amount + 1 làm sentinel.
  • Follow-up: LC 518 đếm số cách (bài 29.8).

Bài tự luyện liên quan

  • LC 518 - Coin Change II (bài 29.8).

29.8 Coin Change II (LC 518)

Đề bài

Đếm số cách gộp amount từ coins (unbounded).

Ví dụ 

Input:  amount=5, coins=[1,2,5]
Output: 4

Ràng buộc

  • 1 <= len(coins) <= 300
  • 1 <= coins[i] <= 5000
  • 0 <= amount <= 5000

Clarifying questions

  • amount = 0? → Trả 1 (1 cách: dùng 0 coin).
  • Tạo permutation thay vì combination? → Đổi outer/inner loop.

Hướng tiếp cận

dp[a] = số cách gộp thành a.

Thứ tự duyệt quan trọng: outer loop coin, inner loop amount → tránh đếm trùng (mỗi combination đếm 1 lần).

Code Python 3 

from typing import List

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1
        for c in coins:
            for a in range(c, amount + 1):
                dp[a] += dp[a - c]
        return dp[amount]

Phân tích độ phức tạp

  • Thời gian: O(amount · n_coins).
  • Bộ nhớ: O(amount).

Bình luận

  • Đảo thứ tự outer/inner sẽ đếm tổ hợp có thứ tự (LC 377).

Bài tự luyện liên quan

  • LC 377 - Combination Sum IV.

29.9 Best Time to Buy and Sell Stock with Cooldown (LC 309)

Đề bài

Mua/bán nhiều lần, sau khi bán phải cooldown 1 ngày mới mua lại được.

Ví dụ 

Input:  prices = [1, 2, 3, 0, 2]   (prices[i] = giá ngày i)
Output: 3   (giao dịch: buy@1 sell@2; cooldown; buy@0 sell@2)

Ràng buộc

  • 1 <= len(prices) <= 5000
  • 0 <= prices[i] <= 1000

Clarifying questions

  • n = 0? → Trả 0.
  • Một ngày duy nhất? → Trả 0 (không bán được).

Hướng tiếp cận

3 state mỗi ngày: hold (đang giữ), sold (vừa bán hôm nay), rest (nghỉ).

  • hold[i] = max(hold[i-1], rest[i-1] - price[i])
  • sold[i] = hold[i-1] + price[i]
  • rest[i] = max(rest[i-1], sold[i-1])

Đáp án = max(sold[-1], rest[-1]).

Code Python 3 

from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices: return 0
        hold = -prices[0]
        sold = 0
        rest = 0
        for p in prices[1:]:
            prev_sold = sold
            sold = hold + p
            hold = max(hold, rest - p)
            rest = max(rest, prev_sold)
        return max(sold, rest)

Phân tích độ phức tạp

  • Thời gian: O(n).
  • Bộ nhớ: O(1).

Bình luận

  • Bẫy: quên cooldown → state sold phải wait 1 day trước khi hold lại.
  • Follow-up: LC 714 (with fee).

Bài tự luyện liên quan

  • LC 121 - Best Time Stock (Chương 1).
  • LC 188 - Stock IV (bài 29.10).

29.10 Best Time to Buy and Sell Stock IV (LC 188)

Đề bài

Tối đa k giao dịch. Max profit.

Ví dụ 

Input:  k=2, prices=[3,2,6,5,0,3]
Output: 7

Ràng buộc

  • 0 <= k <= 100
  • 1 <= len(prices) <= 1000
  • 0 <= prices[i] <= 1000

Clarifying questions

  • k = 0? → Trả 0.
  • k > n/2? → Reduce thành unlimited transactions (LC 122).

Hướng tiếp cận

dp[t][i] = max profit dùng ≤ t giao dịch tới ngày i.

dp[t][i] = max(dp[t][i-1], max(price[i] - price[j] + dp[t-1][j-1]) for j < i).

Tối ưu: theo dõi max_diff = max(dp[t-1][j-1] - price[j]) while iterating.

Code Python 3 

from typing import List

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n = len(prices)
        if n == 0 or k == 0: return 0
        if k >= n // 2:
            # Unlimited transactions.
            return sum(max(prices[i] - prices[i - 1], 0) for i in range(1, n))
        dp = [[0] * n for _ in range(k + 1)]
        for t in range(1, k + 1):
            max_diff = -prices[0]
            for i in range(1, n):
                dp[t][i] = max(dp[t][i - 1], prices[i] + max_diff)
                max_diff = max(max_diff, dp[t - 1][i] - prices[i])
        return dp[k][n - 1]

Phân tích độ phức tạp

  • Thời gian: O(n · k).
  • Bộ nhớ: O(n · k); có thể giảm về O(k).

Bình luận

  • Edge k >= n // 2 → reduce thành unlimited (LC 122).

Bài tự luyện liên quan

  • LC 123 - Stock III (k = 2).

29.11 House Robber II (LC 213)

Đề bài

Tên trộm không thể trộm 2 nhà kề nhau. Nhà xếp vòng tròn (nums[0] và nums[n-1] kề nhau).

Ví dụ 

Input:  nums = [2, 3, 2]   (nums[i] = tiền nhà thứ i, các nhà xếp vòng tròn)
Output: 3   (chỉ trộm được 1 trong 2 nhà đầu/cuối, ở đây trộm 1 nhà giá 3)

Ràng buộc

  • 1 <= len(nums) <= 100
  • 0 <= nums[i] <= 1000

Clarifying questions

  • n = 1? → Trả nums[0].

Hướng tiếp cận

Tách 2 case: trộm hoặc không trộm nhà đầu. - Case 1: trộm nhà 0 → không trộm nhà n-1 → House Robber trên nums[0..n-2]. - Case 2: không trộm nhà 0 → House Robber trên nums[1..n-1].

Đáp án = max của 2.

Code Python 3 

from typing import List

class Solution:
    def rob(self, nums: List[int]) -> int:
        def rob_linear(arr: List[int]) -> int:
            prev = curr = 0
            for x in arr:
                prev, curr = curr, max(curr, prev + x)
            return curr

        if len(nums) == 1: return nums[0]
        return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))

Phân tích độ phức tạp

  • Thời gian: O(n).
  • Bộ nhớ: O(1).

Bình luận

  • Bẫy: vòng tròn → tách 2 case (rob[0] hay không).
  • Follow-up: LC 337 (House Robber III) trên cây - Chương 11.5.

Bài tự luyện liên quan

  • LC 198 - House Robber.
  • LC 337 - House Robber III (Chương 11.5).

29.12 Maximum Product Subarray (LC 152)

Đề bài

Cho nums. Tìm subarray liên tục có tích max.

Ví dụ 

Input:  nums = [2, 3, -2, 4]
Output: 6   (subarray [2, 3] có tích 6 là tích lớn nhất của 1 subarray liên tiếp)

Ràng buộc

  • 1 <= len(nums) <= 2·10^4
  • -10 <= nums[i] <= 10

Clarifying questions

  • All negative? → Trả số ít âm nhất.
  • Có 0? → Reset cur_max/cur_min.

Hướng tiếp cận

Track cả max và min tại mỗi i (vì 2 số âm × nhau ra dương): - cur_max = max(x, x * prev_max, x * prev_min) - cur_min = min(x, x * prev_max, x * prev_min)

Code Python 3 

from typing import List

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        cur_max = cur_min = best = nums[0]
        for x in nums[1:]:
            if x < 0:
                cur_max, cur_min = cur_min, cur_max
            cur_max = max(x, cur_max * x)
            cur_min = min(x, cur_min * x)
            best = max(best, cur_max)
        return best

Phân tích độ phức tạp

  • Thời gian: O(n).
  • Bộ nhớ: O(1).

Bình luận

  • Trick swap khi x < 0: số âm đảo vai trò max/min → ngắn gọn.

Bài tự luyện liên quan

  • LC 53 - Maximum Subarray.

DP III - Partition / Interval DP

29.13 Palindrome Partitioning II (LC 132)

Đề bài

Cho s. Min cuts để chia s thành toàn palindrome.

Ví dụ 

Input:  s = "aab"
Output: 1
(cắt 1 lần thành ["aa", "b"], 2 mảnh đều là palindrome)
Giải thích: Cut thành ["aa", "b"]

Ràng buộc

  • 1 <= len(s) <= 2000
  • s chỉ chứa chữ thường

Clarifying questions

  • s rỗng? → 0 cuts.
  • All palindrome? → 0 cuts.

Hướng tiếp cận

dp[i] = min cuts cho s[0..i]. Pre-compute is_pal[i][j]. Transition: - Nếu s[0..i] đã palindrome → dp[i] = 0. - Ngược lại: dp[i] = min(dp[j-1] + 1 for j <= i if s[j..i] is palindrome).

Code Python 3 

class Solution:
    def minCut(self, s: str) -> int:
        n = len(s)
        is_pal = [[False] * n for _ in range(n)]
        for i in range(n):
            for j in range(i + 1):
                if s[j] == s[i] and (i - j < 2 or is_pal[j + 1][i - 1]):
                    is_pal[j][i] = True

        dp = [0] * n
        for i in range(n):
            if is_pal[0][i]:
                dp[i] = 0
            else:
                dp[i] = min(dp[j - 1] + 1 for j in range(1, i + 1) if is_pal[j][i])
        return dp[n - 1]

Phân tích độ phức tạp

  • Thời gian: O(n²) (precompute palindrome) + O(n²) DP.
  • Bộ nhớ: O(n²).

Bình luận

  • Bẫy: precompute is_palindrome để tránh check lại trong vòng DP chính.
  • Follow-up: LC 131 (Palindrome Partitioning) - backtracking, Chương 28.6.

Bài tự luyện liên quan

  • LC 131 - Palindrome Partitioning (Chương 28.6).

29.14 Burst Balloons (LC 312)

Đề bài

Cho nums đại diện balloon. Nổ mỗi balloon i được điểm nums[i-1] * nums[i] * nums[i+1] (boundary là 1). Max điểm tổng.

Ví dụ 

Input:  nums = [3, 1, 5, 8]   (balloons từ trái sang phải)
Output: 167   (max coin khi nổ tất cả; mỗi lần nổ i được nums[L]*nums[i]*nums[R])

Ràng buộc

  • n == len(nums)
  • 1 <= n <= 300
  • 0 <= nums[i] <= 100

Clarifying questions

  • nums rỗng? → Trả 0.
  • n = 1? → Trả nums[0].

Hướng tiếp cận

Interval DP đảo ngược: thay vì nghĩ “nổ trước cái nào”, nghĩ “nổ cuối cùng cái nào trong interval [i, j]”.

dp[i][j] = max điểm khi nổ tất cả balloon trong (i, j) (exclusive).

dp[i][j] = max(nums[i] * nums[k] * nums[j] + dp[i][k] + dp[k][j]) với k ∈ (i, j).

Pad nums với 1 ở 2 đầu.

Code Python 3 

from typing import List

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        arr = [1] + nums + [1]
        n = len(arr)
        dp = [[0] * n for _ in range(n)]
        for length in range(2, n):
            for i in range(n - length):
                j = i + length
                for k in range(i + 1, j):
                    dp[i][j] = max(dp[i][j],
                                   arr[i] * arr[k] * arr[j] + dp[i][k] + dp[k][j])
        return dp[0][n - 1]

Phân tích độ phức tạp

  • Thời gian: O(n³).
  • Bộ nhớ: O(n²).

Bình luận

  • Insight “nổ cuối cùng” là khoảnh khắc “aha” của bài này. Nếu thử “nổ đầu tiên” sẽ không có optimal substructure (vì sau khi nổ, các balloon còn lại không “biết” có nổ rồi).

Bài tự luyện liên quan

  • LC 1000 - Minimum Cost to Merge Stones.

29.15 Matrix Chain Multiplication (bài kinh điển)

Đề bài

Cho n ma trận A1 · A2 · ... · An với chiều p[i-1] × p[i]. Tìm cách đặt ngoặc để min số phép nhân.

Ví dụ 

Input:  p=[10,20,30,40,30]
Output: 30000

Ràng buộc

  • 1 <= len(matrices) <= 100

Clarifying questions

  • Single matrix? → 0 phép nhân.
  • Dimension không hợp lệ? → Đề bảo đảm hợp lệ.

Hướng tiếp cận

dp[i][j] = min cost nhân A_i · A_{i+1} · ... · A_j. Split tại k: dp[i][j] = min(dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j]).

Code Python 3 

from typing import List

def matrix_chain(p: List[int]) -> int:
    n = len(p) - 1
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for length in range(2, n + 1):
        for i in range(1, n - length + 2):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j])
    return dp[1][n]

Phân tích độ phức tạp

  • Thời gian: O(n³).
  • Bộ nhớ: O(n²).

Bình luận

  • Pattern Interval DP thuần. Cùng template với Burst Balloons.

Bài tự luyện liên quan

  • LC 312 - Burst Balloons (Chương 29.14)
  • LC 1547 - Minimum Cost to Cut a Stick (Chương 29.16)

29.16 Minimum Cost to Cut a Stick (LC 1547)

Đề bài

Stick độ dài n. Mảng cuts là vị trí cần cắt. Cost mỗi lần cắt = chiều dài stick hiện tại. Tìm cost min.

Ví dụ 

Input:  n=7, cuts=[1,3,4,5]
Output: 16

Ràng buộc

  • 2 <= n <= 10^6
  • 1 <= len(cuts) <= min(n-1, 100)

Clarifying questions

  • cuts rỗng? → 0 cost.
  • Cut tại 0 hoặc n? → Theo đề: 1 ≤ cut < n.

Hướng tiếp cận

Sort cuts cộng thêm boundary [0, n]. dp[i][j] = min cost cắt stick từ cuts[i] đến cuts[j]. Try mỗi cut k ∈ (i, j): dp[i][j] = min(dp[i][k] + dp[k][j] + cuts[j] - cuts[i]).

Code Python 3 

from typing import List

class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        cuts = sorted([0] + cuts + [n])
        m = len(cuts)
        dp = [[0] * m for _ in range(m)]
        for length in range(2, m):
            for i in range(m - length):
                j = i + length
                dp[i][j] = min(dp[i][k] + dp[k][j] for k in range(i + 1, j)) + cuts[j] - cuts[i]
        return dp[0][m - 1]

Phân tích độ phức tạp

  • Thời gian: O(m³) với m = len(cuts) + 2.
  • Bộ nhớ: O(m²).

Bình luận

  • Bẫy: quên thêm boundary [0, n] vào cuts → mất thông tin biên.
  • Follow-up: LC 312 (Burst Balloons) cùng pattern Interval DP.

Bài tự luyện liên quan

  • LC 1130 - Minimum Cost Tree From Leaf Values.

29.17 Stone Game VII (LC 1690)

Đề bài

Alice và Bob lần lượt lấy hòn đá ở 2 đầu array. Người lấy được điểm = sum các đá còn lại. Cả 2 chơi optimal. Tìm chênh lệch Alice - Bob.

Ví dụ 

Input:  stones = [5, 3, 1, 4, 2]   (giá trị từng stone, 2 đầu mới được lấy)
Output: 6   (Alice - Bob với cả hai đều chơi tối ưu)

Ràng buộc

  • n == len(stones)
  • 2 <= n <= 1000
  • 1 <= stones[i] <= 1000

Clarifying questions

  • Một stone? → Player 1 lấy, score = 0.

Hướng tiếp cận

Game theory + Interval DP. dp[i][j] = chênh lệch tối ưu khi xét stones [i..j]. Người hiện tại pick lấy điểm sum[i+1..j] (bỏ stones[i]) hoặc sum[i..j-1] (bỏ stones[j]) trừ đi dp[next][next].

Code Python 3 

from functools import cache
from typing import List

class Solution:
    def stoneGameVII(self, stones: List[int]) -> int:
        n = len(stones)
        prefix = [0] * (n + 1)
        for i, s in enumerate(stones):
            prefix[i + 1] = prefix[i] + s

        @cache
        def dp(i: int, j: int) -> int:
            if i >= j: return 0
            # Remove stones[i]: gain = sum của [i+1..j]
            gain_l = prefix[j + 1] - prefix[i + 1]
            # Remove stones[j]: gain = sum của [i..j-1]
            gain_r = prefix[j] - prefix[i]
            return max(gain_l - dp(i + 1, j), gain_r - dp(i, j - 1))

        return dp(0, n - 1)

Phân tích độ phức tạp

  • Thời gian: O(n²).
  • Bộ nhớ: O(n²) cho memo.

Bình luận

  • Bẫy: game-theory DP cần đại diện chính xác “chênh lệch người hiện tại”.
  • Follow-up: LC 1690 chính bài này; LC 877 đơn giản hơn (Stone Game I).

Bài tự luyện liên quan

  • LC 877 - Stone Game (Chương 31).
  • LC 1140 - Stone Game II.

29.18 Strange Printer (LC 664)

Đề bài

Cho s. Máy in mỗi turn in 1 chuỗi gồm cùng 1 ký tự, có thể đè lên cái trước. Tìm số turn tối thiểu để in được s.

Ví dụ 

Input:  s = "aaabbb"
Output: 2   (máy in chỉ in được 1 ký tự liên tiếp 1 lần; tối thiểu 2 lượt)

Ràng buộc

  • 1 <= len(s) <= 100
  • s chỉ chứa chữ thường

Clarifying questions

  • s rỗng? → 0 turn.
  • Toàn 1 ký tự? → 1 turn.

Hướng tiếp cận

Interval DP. dp[i][j] = min turn in s[i..j].

  • Base: dp[i][i] = 1.
  • dp[i][j] = dp[i][j-1] + 1 (in s[j] riêng).
  • Tối ưu: nếu có k < j với s[k] == s[j], có thể “tận dụng” lượt in s[k] để cover s[j] → dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j-1]).

Code Python 3 

class Solution:
    def strangePrinter(self, s: str) -> int:
        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
                dp[i][j] = dp[i][j - 1] + 1
                for k in range(i, j):
                    if s[k] == s[j]:
                        cost = dp[i][k] + (dp[k + 1][j - 1] if k + 1 <= j - 1 else 0)
                        dp[i][j] = min(dp[i][j], cost)
        return dp[0][n - 1]

Phân tích độ phức tạp

  • Thời gian: O(n³).
  • Bộ nhớ: O(n²).

Bình luận

  • Insight “tận dụng turn cũ”: đây là chi tiết tinh tế phân biệt Strange Printer với Palindrome Partitioning.

Bài tự luyện liên quan

  • LC 730 - Count Different Palindromic Subsequences.

Tóm tắt chương & Quyết định

Reading roadmap (chọn 8 bài nếu thiếu thời gian)

  1. House Robber (LC 198) - DP sequence 1D cơ bản.
  2. Coin Change (LC 322) - unbounded knapsack.
  3. Longest Increasing Subsequence (LC 300) - patience.
  4. LCS (LC 1143) - DP 2D trên 2 chuỗi.
  5. Edit Distance (LC 72) - kinh điển.
  6. Best Time IV (LC 188) - stock DP với k giao dịch.
  7. Burst Balloons (LC 312) - interval DP “chọn cuối”.
  8. Stone Game (LC 877) - game DP minimax.

Interval DP - “choose last operation” framing

Burst Balloons / Strange Printer / Matrix Chain: - dp[i][j] = đáp số tối ưu cho range [i..j]. - Hỏi: operation nào thực hiện CUỐI CÙNG trong range này? Lựa chọn k ∈ [i..j] chia thành [i..k-1] và [k+1..j] đã giải xong. - Khác với “chọn đầu tiên” - đa số trường hợp “chọn cuối” cho recurrence sạch hơn.

State table mẫu - LCS (LC 1143)

  "" a b c d e
"" 0 0 0 0 0 0
a 0 1 1 1 1 1
c 0 1 1 2 2 2
e 0 1 1 2 2 3
  • Đường chéo (s1[i] == s2[j]) ⇒ dp[i][j] = dp[i-1][j-1] + 1.
  • Còn lại ⇒ dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

Edit Distance state table - "horse" → "ros"

  "" r o s
"" 0 1 2 3
h 1 1 2 3
o 2 2 1 2
r 3 2 2 2
s 4 3 3 2
e 5 4 4 3

3 phép min(insert, delete, replace) + 1; khớp ký tự → kế thừa chéo.