Lesson 17 — Chia để trị (Divide & Conquer)

Ba module tương tác cho paradigm Divide → Conquer → Combine: cây D&C của Maximum Subarray, Fast Power (chia đôi mũ), và phân biệt D&C (độc lập) với DP (chồng lấp).

1. Cây Divide & Conquer — Maximum Subarray O(n log n)

Bài toán: tìm đoạn con liên tiếp có tổng lớn nhất. D&C cắt đôi tại mid, đoạn tối ưu nằm ở 1 trong 3 chỗ: hoàn toàn trái, hoàn toàn phải, hoặc xuyên giữa. Bấm Bước tiếp để xem chia đôi rồi combine.

trái phải xuyên giữa đang xét

Bấm "Bước tiếp" để bắt đầu.

Mỗi node = một lời gọi maxSubarrayDC(lo, hi). Số trong node là kết quả max của đoạn đó. Combine = max(trái, phải, xuyên giữa).

2. Fast Power — chia đôi mũ O(log n)

Tính x^n không bằng n−1 phép nhân, mà bằng chia đôi mũ: x^n = (x^(n/2))² (n chẵn) hoặc x·(x^(n/2))² (n lẻ). Nhị phân của n quyết định các lũy thừa cần nhân: 13 = 1101₂ → x¹³ = x⁸·x⁴·x¹.

x = n =

Nhập x, n rồi bấm "Tính".

3. D&C vs DP — độc lập hay chồng lấp? paradigm

Khác biệt sống còn: subproblem của D&C độc lập (mỗi node giải 1 lần, cây nở không trùng) vs subproblem của DP chồng lấp (cùng bài con lặp lại nhiều nhánh → cần memo). Chọn ví dụ để so sánh cây đệ quy.

node tính 1 lần node TRÙNG (chồng lấp)

Chọn một ví dụ ở trên.