Giới thiệu
Về câu chuyện của tôi: Khi làm LeetCode hay đi phỏng vấn, gặp bài Dynamic Programming (DP) là tôi... dẹp luôn! Hoặc có đọc solution xong vẫn mơ hồ, kiểu 'Ơ, sao nó lại thế này?'. Bực tức vì tốn thời gian mà chả hiểu gì, tôi quyết định 'học tới nơi tới chốn'. Thế là tôi đào bới tài liệu để học thật kĩ lý thuyết DP.
Bây giờ, tưởng tượng bạn muốn thành 'tỷ phú' ở tuổi 30 với 1 tỷ VND trong tay. Chia cuộc đời thành giai đoạn:
- 18 tuổi: Sống nhờ ba mẹ, tiết kiệm max 600.000 VND/tháng.
- 22 tuổi: Đi làm, max 2.500.000 VND/tháng.
- 25 tuổi: Middle/senior, max 12.000.000 VND/tháng.
- 29 tuổi: SA/tech lead, max 26.000.000 VND/tháng. Tích lũy từng giai đoạn, không lãi suất hay đầu tư, bạn sẽ đạt 1 tỷ đúng hạn. DP cũng vậy: Chia vấn đề lớn thành subproblems nhỏ, tối ưu từng phần để tổng thể tốt nhất.
Lưu ý: DP không phải cấu trúc dữ liệu, mà là phương pháp giải bài toán với subproblems lặp lại và tối ưu. Đừng lo, tôi sẽ giải thích kỹ dưới đây—yên tâm đọc hết, homies sẽ không thất vọng!
Nguyên lý và triết lý của quy hoạch động
Về cơ bản, DP hoạt động khá giống "chia để trị" (divide and conquer) – cái võ công mà các "ông lớn" như merge sort hay quick sort hay dùng. Tức là, từ một bài toán lớn (như tính Fibonacci số lớn), ta chia nhỏ thành các vấn đề con, giải từng cái, rồi ghép lại thành đáp án cuối cùng. Nhưng đời không như mơ, nếu dùng chia để trị thuần túy, bạn sẽ gặp khi các subproblems (vấn đề con) lặp đi lặp lại dẫn đến TLE!
Vậy "subproblems lặp đi lặp lại" là gì? Hãy nhìn vào ví dụ kinh điển: Bài toán Fibonacci. Công thức tổng quát: F(n) = F(n-1) + F(n-2), với F(0) = 0 và F(1) = 1. Nếu vẽ cây đệ quy ra, bạn sẽ thấy:
Các node cùng màu được tính toán lặp đi lặp lại, Khi tính F(5), bạn phải tính F(4) và F(3); nhưng trong F(4) lại tính F(3) lần nữa. Giống như bạn đi chợ mua rau, lần nào cũng tính tiền từ đầu thay vì nhớ giá hôm qua. Kết quả? là mất thời gian và đau đầu để tính (CPU)!
Quy hoạch động tham gia cuộc chơi như một phương pháp powerful nhưng cũng rất bí ẩn để ae luyện thuật toán có thể dễ hiểu được. DP không chỉ chia nhỏ mà còn lưu trữ kết quả từng subproblems để tái sử dụng – kiểu "tính một lần, dùng cả đời".
DP thường dùng cho các bài toán cần đáp án tối ưu (optimal problems), như tìm chuỗi con liên tiếp DÀI NHẤT (Longest Increasing Subsequence), chuỗi chung DÀI NHẤT (Longest Common Subsequence), hay chọn ÍT NHẤT đồ vật để tổng khối lượng LỚN NHẤT (Knapsack problem). Vậy tại sao nó phải là kết quả tối ưu nhất, đối với dạng vấn đề mà quy hoạch động giải quyết thì mỗi problem lớn sẽ giải quyết dựa trên nhiều solutions dựa vào subproblems, và mỗi solution sẽ luôn có một kết quả, chúng ta sẽ phải tìm được solution có kết quả tối ưu nhất (minimize hoặc là maximum). Bên cạnh đó, tại mỗi subproblem được giải, kết quả được "cất tủ" (memoization hoặc tabulation) để sau này lấy ra xài ngay, tránh tính toán lặp.
Đừng lo khi bạn đọc tới đây vẫn bị lú hay tiếp tục các bước giải DP và đọc ví dụ sau đó bạn ngẫm lại statement tôi đã đưa ra thì bạn sẽ hiểu.
Các bước để giải quyết problems bằng DP
Trước khi đến giải các bài toán cụ thể chúng ta sẽ có một khuôn mẫu chung để giải DP như là nhẫn đạo sẽ theo chúng ta suốt đời, hay ghi nhớ thật kĩ các bước này:
- Bước 1: Mô tả cấu trúc của giải pháp tối ưu (Xác định cách subproblems kết hợp để tạo giải pháp toàn cục).
- Bước 2: Định nghĩa đệ quy giá trị giải pháp tối ưu (Xây dựng recurrence relation).
- Bước 3: Tính toán giá trị giải pháp tối ưu theo bottom-up (Sử dụng tabulation để tránh recursion stack và tối ưu thời gian).
Coins Change
Bây giờ chúng ta lấy ví dụ một bài toán leetcode nhập môn cho dạng Dynamic Programming này.
Coins Change là bài toán tìm số lượng đồng xu ít nhất để tạo ra một tổng tiền amount, sử dụng các mệnh giá đồng xu trong mảng coins (có thể dùng không giới hạn mỗi loại). Ví dụ: Với coins = [1,3,4,5] và amount = 7, chúng ta cần tìm cách kết hợp ít xu nhất để tổng = 7. Đây là bài toán tối ưu hóa cổ điển, thường dùng DP vì cách chọn xu ảnh hưởng đến tổng thể.
Lúc đầu đọc qua bài toán tôi thấy bài này dễ như ăn kẹo cứ "greedy" chọn đồng lớn nhất trong số coins và nhỏ hơn lượng amount còn lại là được.
- Amount = 7, tôi chọn 5 (lớn nhất), thì lượng còn lại là 2
- AMount = 2, tôi chọn 1, thì lượng còn lại là 1
- Amount = 1, tôi tiếp tục chọn 1 vì không còn số coins nào nhỏ hơn, và lượng còn lại là 0.
Vậy là tôi đã có đáp án là 3 xu [5, 1, 1], tôi tự tin submit và sau đó kết quả là chỉ cần 2 xu [4, 3] trước sự ngỡ ngàng của tôi, rõ ràng sự tham lam "greedy" đã không cho tôi đáp án đúng. Vậy sai ở đâu? Greedy "tham" chọn 5 đầu tiên, nhưng bỏ lỡ cách tốt hơn: 4 + 3 = 7 (chỉ 2 xu). Giống như bạn "tham" mua nhà to ngay, nhưng hết tiền không mua nổi xe!
Bây giờ chúng ta sẽ xem qua các bước chọn số đồng xu được cho trước sao cho tổng mệnh giá là 7:
Bước 1: Mô tả cấu trúc của giải pháp tối ưu (Xác định cách subproblems kết hợp để tạo giải pháp toàn
Chúng ta sẽ quy bài toán về dạng tổng quat là T(coins, amount), Rõ ràng chúng ta thấy rằng với một đồng xu i được chọn từ đống coins , thì chúng ta di chuyển bài toán tìm số đồng lượng xu với tổng mệnh giá bằng amount -i, Tức là vấn đề chính sẽ phụ thuộc vào subproblem amount - i, ví dụ:
- Với amount = 7, tôi có 1 lựa chọn là 5, thì tôi sẽ giải quyết tiếp tục bài toán con là: T(coins, 7) = 1 + T(coins, 7 - 5)
- Với amount = 2, tôi có 1 lựa chọn là 1: T(coins, 7) = 1 + T(coins, 2 - 1)
- Với amount = 1, tôi có 1 lựa chọn là 1: T(coins, 7) = 1 + T(coins, 1 - 1)
- Tới đây amount = 0 nên chúng ta sẽ dừng tính toán
Bước 2: Định nghĩa đệ quy giá trị giải pháp tối ưu (Xây dựng recurrence relation).
Nhưng đối với amount = 7 và tôi không chỉ có 1 sự lựa chọn là bốc đồng xu mệnh giá = 5, tôi có thể bốc xu mệnh giá = 4 hoặc mệnh giá = 3, mệnh giá bằng 1 miễn sao các coin i này bé hơn amount và i là 1 trong giá trị của coins , vậy chúng ta có thể suy ra để tính được kết quả tối ưu cho mệnh giá 7 thì chúng ta phải chọn được kết quả tối ưu giữa một tập hợp subproblems.
Tức là với mọi i trong coins tức là {i0, i1, i2, ...., ik}: T(n) = min {1 + T(n-i0), 1 + T(n-i1), .... , 1 +T(n - ik)}
T(coins, amount) = min(1 + T(coins, amount - i))
Bước 3: Tính toán giá trị giải pháp tối ưu theo bottom-up.
Bây giờ đến phần "thú vị" nhất - sau khi đã có cấu trúc (Bước 1) và công thức đệ quy (Bước 2), chúng ta sẽ "xây nhà từ móng lên mái" thay vì "mơ mộng từ mái xuống móng". Bottom-up giống như cách bạn tiết kiệm tiền, bắt đầu từ 0 đồng, tích lũy dần từng tháng một cách có hệ thống, thay vì mơ về 1 tỷ rồi tính ngược lại. Với ví dụ coins =[1,3,4,5] và amount = 7, chúng ta sẽ:
- Khởi tạo mảng dp[0..7]: dp[i] = số xu ít nhất để tạo ra amount i
- dp = 0 (base case: không cần xu nào để tạo ra 0)
- dp[i] = ∞ với i > 0 (ban đầu coi là không thể)
- Loop từ amount = 1 đến 7: Với mỗi amount hiện tại, thử tất cả coins
csao cho với mỗi coincmà c <= amount:- Cập nhật dp[amount] = min(dp[amount], dp[amount - c] + 1)
- Nghĩa là: "Nếu dùng coin c, tôi cần 1 + số xu tối thiểu cho (amount - c)"
| Amount | Min Coins | Coin Used | Updated From Amount | Giải Thích Chi Tiết |
|---|---|---|---|---|
| 0 | 0 | - | - | Base case: Không cần xu nào để tạo ra 0 |
| 1 | 1 | 1 | 0 | Chỉ có coin=1 ≤ 1, nên dp[1] = dp[0] + 1 = 1 |
| 2 | 2 | 1 | 1 | Chỉ có coin=1 ≤ 2, nên dp[2] = dp[2-1] + 1 = 2 (dùng 1+1) |
| 3 | 1 | 3 | 0 | Thử coin=1: dp[3-1]+1=3; coin=3: dp[3-3]+1=1 → min=1 |
| 4 | 1 | 4 | 0 | Thử coin=1: dp[4-1]+1=2; coin=3: dp[4-3]+1=2; coin=4: dp[4-4]+1=1 → min=1 |
| 5 | 1 | 5 | 0 | Thử tất cả coins, coin=5: dp[5-5]+1=1 là nhỏ nhất → min=1 |
| 6 | 2 | 3 | 3 | Thử coin=1: dp[6-1]+1=2; coin=3: dp[6-3]+1=2; coin=4: dp[6-4]+1=3; coin=5: dp[6-5]+1=2 → min=2 |
| 7 | 2 | 3 | 4 | Thử coin=1: dp[7-1]+1=3; coin=3: dp[7-3]+1=2; coin=4: dp[7-4]+1=2; coin=5: dp[7-5]+1=3 → min=2 |
Code
ALGORITHM: CoinChange(coins[], amount)
INPUT: coins[] - mảng các mệnh giá đồng xu amount - số tiền cần đổi OUTPUT: Số lượng đồng xu tối thiểu (hoặc -1 nếu không thể) BEGIN // Bước 1: Khởi tạo mảng DP CREATE dp[] of size (amount + 1) dp[0] = 0 // Base case FOR i = 1 TO amount DO dp[i] = INFINITY // Khởi tạo với giá trị vô cùng END FOR // Bước 2: Tính toán bottom-up FOR currentAmount = 1 TO amount DO FOR each coin IN coins DO IF coin <= currentAmount AND dp[currentAmount - coin] != INFINITY THEN dp[currentAmount] = MIN(dp[currentAmount], dp[currentAmount - coin] + 1) END IF END FOR END FOR // Bước 3: Trả về kết quả IF dp[amount] == INFINITY THEN RETURN -1 // Không thể tạo ra amount ELSE RETURN dp[amount] // Số xu tối thiểu END IF
END
Bước 1: Khởi Tạo (Initialization)
CREATE dp[] of size (amount + 1)
dp[0] = 0
FOR i = 1 TO amount: dp[i] = INFINITY
- Tạo mảng dp có kích thước amount + 1 để chứa kết quả subproblems
- dp = 0 vì không cần xu nào để tạo ra amount = 0 (base case)
- Các giá trị khác khởi tạo = INFINITY để đánh dấu "chưa tính được"
Bước 2: Tính Toán Bottom-Up
FOR currentAmount = 1 TO amount: FOR each coin IN coins: IF coin <= currentAmount AND dp[currentAmount - coin] != INFINITY: dp[currentAmount] = MIN(dp[currentAmount], dp[currentAmount - coin] + 1)
- Duyệt từ amount = 1 đến target amount
- Với mỗi amount, thử tất cả coins có thể sử dụng
- Diều kiện: coin <= currentAmount (coin không vượt quá amount hiện tại)
- Cập nhật: dp[currentAmount] = MIN(giá trị cũ, dp[currentAmount - coin] + 1)
Bước 3: Trả Về Kết Quả
IF dp[amount] == INFINITY: RETURN -1
ELSE: RETURN dp[amount]
- Nếu dp[amount] vẫn là INFINITY, nghĩa là không thể tạo ra amount với các coins cho trước
- Ngược lại, trả về số xu tối thiểu đã tính được
Time Complexity: O(amount × number_of_coins) Space Complexity: O(amount)
Tổng kết
Vậy là chúng ta đã đi qua khuôn mẫu chung để giải quyết các bài toán quy hoạch động, phần sau tôi sẽ tổng hợp các pattern của các bài toán quy hoạch động và kèm theo các dạng leetcode để ae ôn luyện.