1.1 Dynamic Programming là gì?

Ví dụ Fibonacci

Tính fib(n) = fib(n-1) + fib(n-2). Đệ quy ngây thơ tính fib(2) rất nhiều lần (overlapping). Cache → mỗi state tính 1 lần → từ O(2ⁿ) xuống O(n).

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

• "Đếm số cách", "tìm tối ưu (min/max)" với input có cấu trúc tuần tự.
• Bài có thể giải bằng đệ quy nhưng tốn exp time vì lặp lại.
• Decision tại mỗi bước phụ thuộc vào kết quả các bước trước.
• Có thể đặt câu hỏi: "Nếu biết kết quả của các state nhỏ hơn, làm sao tính state hiện tại?" Trả lời được = DP áp dụng được.

1.2 Memoisation (Top-down) vs Tabulation (Bottom-up)

Aspect	Memoisation	Tabulation
Hướng tính	Lớn → nhỏ (đệ quy với cache)	Nhỏ → lớn (vòng for điền bảng)
Cú pháp	Đệ quy + dict/@lru_cache	Mảng dp[] + nested loops
Khởi tạo	Cache rỗng + base case trong if	Init bảng + base case explicit
Chỉ tính state cần	✓	✗ Tính hết
Stack overflow	Có thể với n lớn	Không bao giờ
Space optimisation	Khó	Dễ — rolling array O(1)
Phỏng vấn	Dễ viết hơn từ recursion	Production-ready

Quy tắc chuyển đổi

• Memoisation thường viết trước — chuyển recursion + cache là đủ.
• Tabulation = unroll memoisation theo chiều ngược.
• Khi đã có tabulation, có thể tối ưu space bằng cách giữ chỉ các state cần.

1.3 Quy trình thiết kế DP — 5 bước

1. Định nghĩa state: dp[i] nghĩa là gì? Ví dụ: "dp[i] = số cách lên tới bậc thứ i".
2. Viết recurrence: dp[i] = ? dựa trên dp[i-1], dp[i-2], ... Ví dụ: dp[i] = dp[i-1] + dp[i-2].
3. Xác định base case: dp[0], dp[1], ... Ví dụ: dp[0] = 1, dp[1] = 1.
4. Quyết định thứ tự tính: từ nhỏ đến lớn (tabulation) hay đệ quy (memoisation).
5. Tối ưu space (nếu có thể): chỉ giữ các state cần. Ví dụ Fibonacci chỉ cần 2 biến.

1.4 Backtracking vs DP — Khi nào chuyển?

Tuần 11 đã thấy backtracking giải mọi bài "liệt kê khả năng". Khi nào chuyển sang DP?

Backtracking	DP
Cần liệt kê tất cả nghiệm	Cần đếm hoặc tìm tối ưu
Mỗi state thăm 1 lần	Cùng state thăm nhiều lần (overlapping)
Output lớn (exp)	Output nhỏ (số / boolean)
Time exp	Time poly nhờ cache

Quy trình chuyển đổi

1. Bắt đầu với backtracking (ngây thơ).
2. Nhận diện state state = các tham số tham gia quyết định kết quả.
3. Add @lru_cache vào hàm đệ quy → instant memoisation.
4. Convert sang tabulation nếu cần tối ưu space.

Đa số bài DP có lời giải Memoisation viết được trong < 5 phút từ backtracking. Đó là lý do nên thuộc backtracking trước (Tuần 11).

2.1 Linear DP Pattern

Mẫu chung

n = len(input)
dp = [0] * (n + 1)
dp[0] = base_case
for i in range(1, n + 1):
    dp[i] = recurrence(dp[i-1], dp[i-2], ..., input[i-1])
return dp[n]

Tối ưu space O(1)

Khi recurrence chỉ dùng vài state cuối, có thể bỏ mảng dp, chỉ giữ vài biến:

prev2, prev1 = base_0, base_1
for i in range(2, n + 1):
    cur = recurrence(prev1, prev2)
    prev2, prev1 = prev1, cur
return prev1

Pattern này giảm O(n) space xuống O(1) — lợi rõ khi n lớn.

2.2 Worked Example 1 — Climbing Stairs (#70)

Đề: n bậc thang. Mỗi bước có thể leo 1 hoặc 2 bậc. Có bao nhiêu cách lên đỉnh?

Phân tích

State: dp[i] = số cách lên đến bậc i. Recurrence: để đến bậc i, hoặc từ bậc i-1 (1 bước) hoặc từ i-2 (2 bước):

$$ dp[i] = dp[i-1] + dp[i-2] $$

Đây chính là Fibonacci.

Ba cách

# Cách 1 — Đệ quy ngây thơ — O(2ⁿ), TLE
def climbStairs_naive(n):
    if n <= 2: return n
    return climbStairs_naive(n-1) + climbStairs_naive(n-2)

# Cách 2 — Memoisation — O(n)
from functools import lru_cache
@lru_cache(None)
def climbStairs_memo(n):
    if n <= 2: return n
    return climbStairs_memo(n-1) + climbStairs_memo(n-2)

# Cách 3 — Tabulation O(1) space — chuẩn vàng
def climbStairs(n):
    if n <= 2: return n
    a, b = 1, 2                      # dp[1], dp[2]
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b

2.3 Fibonacci (#509) — Cây đệ quy minh hoạ

Tại sao đệ quy ngây thơ là O(2ⁿ)?

Cây đệ quy fib(5) — fib(3) tính 2 lần, fib(2) tính 3 lần. Với n lớn, sự lặp lại phát triển theo cấp số mũ.

Memoisation cache fib(3) sau lần đầu → các lần sau tra O(1) → tổng O(n). Đây là tinh thần cốt lõi của DP.

2.4 Worked Example 3 — House Robber (#198)

Đề: Mảng nums[i] = giá trị nhà thứ i. Không được cướp hai nhà liền kề. Tìm giá trị tối đa cướp được.

Phân tích state

State: dp[i] = giá trị tối đa cướp được trong nums[0..i].

Recurrence — tại nhà i, có 2 lựa chọn:

• Cướp nhà i: phải bỏ qua nhà i-1 → giá trị = dp[i-2] + nums[i].
• Bỏ qua nhà i: dp[i] = dp[i-1].

$$ dp[i] = \max(dp[i-1], \, dp[i-2] + \text{nums}[i]) $$

def rob(nums):
    if not nums: return 0
    if len(nums) == 1: return nums[0]
    prev2 = nums[0]
    prev1 = max(nums[0], nums[1])
    for i in range(2, len(nums)):
        cur = max(prev1, prev2 + nums[i])
        prev2, prev1 = prev1, cur
    return prev1

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

2.5 House Robber — Trace tay

nums = [2, 7, 9, 3, 1]. Kỳ vọng: 12 (nhà 1, 3, 5: 2+9+1, hoặc 2, 4: 7+3 = 10 — kết quả tối ưu là 2+9+1 = 12).

i	nums[i]	prev2	prev1	cur = max(prev1, prev2+nums[i])
0	2	—	2	—
1	7	2	7	—
2	9	2	7	max(7, 2+9) = 11
3	3	7	11	max(11, 7+3) = 11
4	1	11	11	max(11, 11+1) = 12

Trả 12 ✓. Đường: cướp nhà 0 (2) + nhà 2 (9) + nhà 4 (1) = 12.

2.6 Worked Example 4 — House Robber II (Circular) (#213)

Đề: Như #198 nhưng các nhà nối thành vòng tròn — nhà 0 và nhà n-1 liền kề.

Mẹo: Chia thành 2 bài tuyến tính

Vì nhà 0 và nhà n-1 không thể cướp cùng lúc, đáp án = max của:

• Cướp trên nums[0..n-2] (bao gồm 0, không có n-1).
• Cướp trên nums[1..n-1] (không có 0, bao gồm n-1).

def rob(nums):
    if len(nums) == 1: return nums[0]
    def rob_linear(arr):
        prev2 = prev1 = 0
        for x in arr:
            prev2, prev1 = prev1, max(prev1, prev2 + x)
        return prev1
    return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))

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

Knowledge Check — Linear DP

3.1 Choice DP — Pattern Knapsack

Hai loại knapsack

• 0/1 Knapsack: mỗi item chỉ được dùng 0 hoặc 1 lần.
• Unbounded Knapsack: mỗi item được dùng nhiều lần.

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

• "Tổng = target với items đã cho", "min number to reach target".
• "Có thể chọn lại item không?" → quyết định 0/1 hay unbounded.
• Coin Change (#322) — unbounded; Partition Equal Subset Sum (#416) — 0/1.

3.2 Worked Example 5 — Coin Change (#322, Min Coins)

Đề: Mảng coins (mệnh giá), số amount. Tìm số coins tối thiểu để cấu thành amount. Mỗi coin có thể dùng nhiều lần. -1 nếu không thể.

State design

dp[i] = số coins tối thiểu để cấu thành i. Base: dp[0] = 0.

Recurrence: với mỗi coin, nếu i ≥ coin, có thể dùng coin đó:

$$ dp[i] = \min_{c \in \text{coins}} \{ dp[i - c] + 1 \} $$

def coinChange(coins, amount):
    INF = amount + 1                       # giá trị "không thể đạt"
    dp = [INF] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for c in coins:
            if c <= i:
                dp[i] = min(dp[i], dp[i - c] + 1)
    return dp[amount] if dp[amount] != INF else -1

Time O(amount × len(coins)), Space O(amount).

3.3 Coin Change — Trace tay

coins = [1, 2, 5], amount = 11. Kỳ vọng: 3 (5+5+1).

i	dp[i] = min(dp[i-1]+1, dp[i-2]+1, dp[i-5]+1)	Kết quả
0	—	0
1	min(dp[0]+1) = 1	1
2	min(dp[1]+1, dp[0]+1) = 1	1
3	min(dp[2]+1, dp[1]+1) = 2	2
4	min(dp[3]+1, dp[2]+1) = 2	2
5	min(dp[4]+1, dp[3]+1, dp[0]+1) = 1	1
6	min(dp[5]+1, dp[4]+1, dp[1]+1) = 2	2
7	min(...) = 2 (5+2)	2
...	...	...
10	min(...) = 2 (5+5)	2
11	min(dp[10]+1, dp[9]+1, dp[6]+1) = 3	3 ✓

Đường: 11 = 5 + 5 + 1 → 3 coins.

3.4 Worked Example 6 — Coin Change 2 (#518, Number of Ways)

Đề: Mảng coins, amount. Đếm số cách cấu thành amount. Mỗi coin dùng nhiều lần. Combinations (không quan tâm thứ tự).

def change(amount, coins):
    dp = [0] * (amount + 1)
    dp[0] = 1                              # 1 cách: không dùng coin nào
    for c in coins:                        # OUTER: coins
        for i in range(c, amount + 1):     # INNER: amount
            dp[i] += dp[i - c]
    return dp[amount]

Trace với coins = [1, 2, 5], amount = 5

Sau	dp[0]	dp[1]	dp[2]	dp[3]	dp[4]	dp[5]
Init	1	0	0	0	0	0
Coin 1	1	1	1	1	1	1
Coin 2	1	1	2	2	3	3
Coin 5	1	1	2	2	3	4

Kết quả: 4 cách (5; 2+2+1; 2+1+1+1; 1+1+1+1+1).

3.5 #322 vs #518 — Khác biệt loop order

Hai bài cùng pattern unbounded knapsack nhưng thứ tự loop khác nhau:

Bài	Outer loop	Inner loop	Lý do
#322 (min coins)	amount	coins	Mỗi i, thử mọi coin → tìm min
#518 (đếm cách)	coins	amount	Tránh đếm trùng cùng combination

Vì sao #518 phải outer = coins?

Nếu đảo (outer = amount, inner = coins), sẽ đếm permutations (1+2 và 2+1 là 2 cách khác). Outer = coins thì khi xử lý coin 2, ta dùng dp[i-2] đã là kết quả "chỉ dùng coin 1 và 2", không có coin 5 — đảm bảo combination unique.

3.6 Worked Example 7 — Word Break (#139)

Đề: String s, wordDict. Trả True nếu có thể chia s thành chuỗi từ trong dict (cho phép dùng lại).

Ví dụ: s = "leetcode", wordDict = ["leet", "code"] → True.

State

dp[i] = True nếu s[0..i-1] có thể phân chia.

Recurrence: dp[i] = True nếu tồn tại j < i sao cho dp[j] = True và s[j..i-1] ∈ wordDict.

def wordBreak(s, wordDict):
    word_set = set(wordDict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break                      # tìm thấy một cách là đủ
    return dp[n]

Time O(n² × L) (L = chi phí slice + lookup), Space O(n).

Knowledge Check — Knapsack DP

4.1 Subsequence DP — Pattern

Tín hiệu

• "Longest increasing/common subsequence".
• "Maximum subarray sum".
• "Number of ways with constraint at each step".

Hai loại state design phổ biến

1. dp[i] = best ending at i: phần tử cuối cùng là i. Cần lấy max(dp) cuối cùng. Áp dụng cho LIS, Maximum Subarray.
2. dp[i] = best in prefix [0..i]: bao gồm bất kỳ phần tử nào trong tiền tố. Ans = dp[n-1]. Áp dụng cho House Robber.

Khi nào chọn cái nào? Nếu recurrence cần biết "phần tử cuối là gì" (như LIS so sánh giá trị) → loại 1. Nếu không cần → loại 2.

4.2 Worked Example 8 — Longest Increasing Subsequence (LIS)

Đề (LeetCode #300): Mảng nums. Tìm độ dài subsequence tăng dài nhất (không nhất thiết liên tiếp).

Ví dụ: [10, 9, 2, 5, 3, 7, 101, 18] → 4 (chuỗi [2,3,7,101] hoặc [2,5,7,18]).

Approach DP O(n²)

State: dp[i] = độ dài LIS kết thúc tại i.

Recurrence: dp[i] = max(dp[j]) + 1 với j < i và nums[j] < nums[i].

def lengthOfLIS(nums):
    n = len(nums)
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

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

4.3 LIS — Tối ưu O(n log n) bằng Patience Sorting

Khi n = 10⁵, O(n²) = 10¹⁰ → TLE. Cần O(n log n).

Ý tưởng

Duy trì mảng tails với tails[k] = phần tử nhỏ nhất có thể là cuối của subsequence dài k+1.

Với mỗi x: tìm vị trí trong tails để thay (lower_bound):

• Nếu x lớn hơn mọi phần tử trong tails → append (tăng độ dài LIS).
• Ngược lại → thay phần tử đầu tiên ≥ x.

from bisect import bisect_left
def lengthOfLIS(nums):
    tails = []
    for x in nums:
        idx = bisect_left(tails, x)
        if idx == len(tails):
            tails.append(x)
        else:
            tails[idx] = x
    return len(tails)

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

4.4 Worked Example 9 — Maximum Subarray (Kadane's)

Đề (LeetCode #53): Mảng nums. Tìm subarray liên tiếp có tổng lớn nhất.

Kadane's Algorithm — DP O(n) O(1)

State: dp[i] = tổng max của subarray kết thúc tại i.

Recurrence: tại i, hoặc kế tục subarray cũ (dp[i-1] + nums[i]) hoặc bắt đầu mới (nums[i]):

$$ dp[i] = \max(dp[i-1] + \text{nums}[i], \, \text{nums}[i]) $$

def maxSubArray(nums):
    cur = best = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)
        best = max(best, cur)
    return best

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

4.5 Worked Example 10 — Best Time to Buy and Sell Stock with Cooldown

Đề (LeetCode #309): Mảng prices. Mua/bán cổ phiếu nhiều lần. Sau khi bán, phải nghỉ 1 ngày trước khi mua lại. Tối đa lợi nhuận.

State Machine DP

3 trạng thái có thể tại mỗi ngày:

• hold[i] — đang giữ cổ phiếu cuối ngày i.
• sold[i] — vừa bán hôm nay (ngày i).
• rest[i] — không giữ + không vừa bán.

$$ \text{hold}[i] = \max(\text{hold}[i-1], \text{rest}[i-1] - \text{prices}[i]) $$ $$ \text{sold}[i] = \text{hold}[i-1] + \text{prices}[i] $$ $$ \text{rest}[i] = \max(\text{rest}[i-1], \text{sold}[i-1]) $$

def maxProfit(prices):
    if not prices: return 0
    hold = -prices[0]; sold = 0; rest = 0
    for i in range(1, len(prices)):
        new_hold = max(hold, rest - prices[i])
        new_sold = hold + prices[i]
        new_rest = max(rest, sold)
        hold, sold, rest = new_hold, new_sold, new_rest
    return max(sold, rest)

Knowledge Check — Subsequence DP

5.0 Decision Tree — 1D DP

Tín hiệu trong đề	Pattern
"số cách lên bậc/đếm path"	Linear DP: dp[i] = dp[i-1] + dp[i-2]
"max/min với constraint liền kề"	House Robber pattern: dp[i] = max(dp[i-1], dp[i-2]+x)
"vòng tròn / circular"	Tách thành 2 bài tuyến tính
"min coins/items để đạt target"	Coin Change (#322): dp[i] = min(dp[i-c]+1)
"đếm số cách combinations"	Coin Change 2 (#518): outer items, inner capacity
"đếm số cách permutations"	Climbing Stairs / Combination Sum IV
"có thể phân chia / break"	Word Break: dp[i] = OR(dp[j] AND s[j:i] valid)
"longest increasing/non-decreasing"	LIS: O(n²) DP hoặc O(n log n) patience
"max subarray sum"	Kadane's: O(n) O(1)
"buy/sell stock với constraint"	State Machine DP (hold/sold/rest)

Quy trình code DP

1. Định nghĩa state.
2. Viết recurrence (kèm base case).
3. Cài memoisation trước (dễ hơn).
4. Convert tabulation nếu cần tối ưu space.
5. Tối ưu O(1) space nếu chỉ dùng vài state cuối.

Tổng kết Tuần 12

Đã học

• DP fundamentals: optimal substructure + overlapping subproblems; memoisation vs tabulation.
• Quy trình 5 bước: state → recurrence → base case → thứ tự tính → tối ưu space.
• Linear DP: Climbing Stairs, Fibonacci, House Robber I/II — tối ưu O(1) space.
• Knapsack-like DP: Coin Change min/count, Word Break — quy tắc loop order combinations vs permutations.
• Subsequence DP: LIS O(n²) và O(n log n) patience sorting; Kadane's O(n) O(1).
• State Machine DP: Stock with Cooldown — nhiều state mỗi bước.
• Cầu nối từ Backtracking: thêm @lru_cache để biến exp → poly khi có overlapping.

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

1. LeetCode #70 — Climbing Stairs
2. LeetCode #509 — Fibonacci Number
3. LeetCode #198 — House Robber
4. LeetCode #213 — House Robber II
5. LeetCode #322 — Coin Change (min)
6. LeetCode #518 — Coin Change 2 (count)
7. LeetCode #139 — Word Break
8. LeetCode #300 — Longest Increasing Subsequence (cả 2 approach)
9. LeetCode #53 — Maximum Subarray (Kadane's)
10. LeetCode #309 — Best Time to Buy and Sell Stock with Cooldown
11. LeetCode #91 — Decode Ways
12. LeetCode #152 — Maximum Product Subarray