Đang tải trang
Trong bài này
Minh cần đếm số cách leo 5 bậc thang, mỗi lần đi 1 hoặc 2 bậc. Minh thấy nhiều đường đi cùng ghé một bậc, nên muốn tái sử dụng số cách đã tính.
Bài toán con lặp khiến đệ quy làm lại công việc
Số Fibonacci thứ n được định nghĩa bởi F(0) = 0, F(1) = 1 và F(n) = F(n-1) + F(n-2) khi n >= 2. Đệ quy trực tiếp bám sát định nghĩa nhưng tính cùng giá trị nhiều lần.
Hai đỉnh ghi F2 là hai lần gọi độc lập. Đây là bài toán con chồng lặp (overlapping subproblems): cùng câu hỏi xuất hiện ở nhiều nhánh.
Đoạn sau tự đếm mọi lần vào hàm, kể cả lần trả về ngay. Nó so sánh đệ quy trực tiếp với cách lưu kết quả cho cùng đầu vào.
Python
calls_plain = 0
def plain(n):
global calls_plain
calls_plain += 1
if n < 2:
return n
return plain(n - 1) + plain(n - 2)
calls_saved = 0
memo = {}
def saved(n):
global calls_saved
calls_saved += 1
if n not in memo:
memo[n] = n if n < 2 else saved(n - 1) + saved(n - 2)
return memo[n]
print(plain(10), calls_plain)
print(saved(10), calls_saved, len(memo))Kết quả
55 177 55 19 11
Với n = 10, hai hàm cùng trả 55. Hàm đầu vào 177 lần; hàm sau vào 19 lần nhưng chỉ tính 11 trạng thái khác nhau. Số lần vào và số trạng thái không đồng nghĩa: có lần vào chỉ lấy giá trị đã lưu.
Quy hoạch động (dynamic programming, viết tắt DP) giải các trạng thái liên quan và tái sử dụng kết quả. Không phải mọi đệ quy đều cần DP: nếu các nhánh không gặp lại trạng thái nào, lưu bảng có thể không tiết kiệm công việc.
Điều kiện tiếp theo là kết quả của trạng thái phải được xây đúng từ các trạng thái nhỏ hơn. Với bài tối ưu, một lời giải tối ưu cần có thể ghép từ lời giải tối ưu của phần còn lại. Nếu thông tin đã lưu bỏ sót điều kiện ảnh hưởng tương lai, hai tình huống tưởng giống nhau có thể cần đáp án khác nhau.
Bốn câu hỏi xác định một bảng có nghĩa
Trước khi viết vòng lặp, bạn trả lời bốn câu hỏi sau bằng lời cụ thể.
Trạng tháiMột ô mô tả chính xác câu hỏi nào?Cơ sởCâu hỏi nhỏ nhất có đáp án gì?Chuyển tiếpNhững lựa chọn cuối tạo ra ô này?Thứ tựCác ô cần dùng đã có kết quả chưa?
Trạng thái (state) là thông tin đủ để xác định một bài toán con. Trường hợp cơ sở (base case) là trạng thái có đáp án biết trực tiếp. Chuyển tiếp (transition) kết hợp các trạng thái đã biết. Thứ tự tính (evaluation order) phải tôn trọng quan hệ phụ thuộc đó.
Chẳng hạn, nếu chi phí đi tiếp còn phụ thuộc số vé đã dùng, chỉ lưu vị trí là chưa đủ. Hai người cùng đứng tại một bậc nhưng còn số vé khác nhau không nhất thiết có cùng lựa chọn sau đó. Khi ấy, trạng thái cần thêm thông tin về vé.
Đếm cách và tìm giá trị nhỏ nhất cũng cần phép gộp khác nhau. Các nhóm đường đi rời nhau được cộng; các ứng viên chi phí được so sánh bằng min. Cần chứng minh các lựa chọn bao hết mọi khả năng và không đếm trùng khi cộng.
Bước cuối giúp đếm cách leo cầu thang
Quy ước bậc xuất phát là 0. Mỗi lần đi lên 1 hoặc 2 bậc; thứ tự bước tạo thành cách khác nhau. Không bước nào là một cách ở bậc 0.
Đặt dp[i] là số cách đứng đúng ở bậc i. Cơ sở là dp[0] = 1 và dp[1] = 1. Khi i >= 2, bước cuối đến từ i-1 hoặc i-2, nên dp[i] = dp[i-1] + dp[i-2].
Hai nhóm không giao nhau vì độ dài bước cuối khác nhau. Bỏ bước cuối khỏi một đường đi cho đúng một đường tới bậc trước đó. Ngược lại, nối bước cuối phù hợp vào mỗi đường cũ tạo đúng một đường mới.
Để thấy phép cộng hoạt động, xét bậc 4. Có ba đường tới bậc 3 và hai đường tới bậc 2. Nối bước dài 1 vào từng đường của nhóm thứ nhất tạo ba đường tới bậc 4. Nối bước dài 2 vào nhóm thứ hai tạo thêm hai đường, nên có năm đường.
Không được cộng số bậc trước thay cho số đường tới các bậc đó. Chỉ số cho biết vị trí; giá trị trong ô cho biết số cách. Tương tự, dp[0] = 1 không nói có một bước dài 0. Nó nói chỉ có một dãy bước rỗng để ở vị trí xuất phát.
7 dòng
| Bậc | Số cách |
|---|---|
| 0 | 1 |
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 5 |
| 5 | 8 |
| 6 | 13 |
Với 5 bậc, bảng cho 8 cách. Tính từ trái sang phải vì ô hiện tại cần hai ô nhỏ hơn. Đoạn dưới đọc n, kể cả trường hợp không có bậc nào.
Dữ liệu vào
5
Python
n = int(input())
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
dp[i] = dp[i - 1]
if i >= 2:
dp[i] += dp[i - 2]
print(dp[n])Kết quả
8
Mỗi bậc cần tối đa hai phép cộng, nên có O(n) phép toán và O(n) ô nhớ. Với n = 1000, số lần cập nhật không vượt 1000. Số nguyên chính xác lớn dần, nên phép cộng không có chi phí bit cố định; đề thi thường yêu cầu lấy dư để giới hạn kích thước.
Ghi nhớ và lập bảng khác nhau ở hướng tính
Ghi nhớ (memoization) bắt đầu từ câu hỏi lớn rồi tính các trạng thái cần đến. Từ điển lưu kết quả để lần hỏi sau không tính lại. Khóa phải chứa đủ thông tin quyết định đáp án.
Python
memo = {0: 0, 1: 1}
def fib(n):
if n not in memo:
memo[n] = fib(n - 1) + fib(n - 2)
return memo[n]
print(fib(8))
print(sorted(memo.items()))Kết quả
21 [(0, 0), (1, 1), (2, 1), (3, 2), (4, 3), (5, 5), (6, 8), (7, 13), (8, 21)]
Chỉ số n là đủ vì định nghĩa Fibonacci không phụ thuộc dữ liệu thay đổi khác. Nếu kết quả còn phụ thuộc một danh sách thay đổi, dùng lại bộ nhớ cũ có thể sai. Hàm đệ quy vẫn dùng ngăn xếp lời gọi; với độ sâu lớn, giới hạn đệ quy Python có thể gây lỗi.
Ví dụ, giả sử một hàm hỏi chi phí nhỏ nhất từ vị trí i với bảng phí cố định. Khi thay bảng phí cho một cầu thang khác, kết quả cũ theo khóa i không còn đại diện cùng câu hỏi. Có thể tạo từ điển mới cho từng cầu thang hoặc đưa dữ liệu quyết định đáp án vào thiết kế khóa phù hợp.
Không nên dùng phép kiểm tra kiểu “giá trị đã lưu có khác 0 không” để xác định một ô đã tính. Kết quả hợp lệ có thể bằng 0, chẳng hạn F(0). Kiểm tra sự có mặt của khóa giúp phân biệt giá trị 0 với trạng thái chưa có kết quả.
Lập bảng (tabulation) đi từ cơ sở lên các trạng thái lớn. Cách này tránh ngăn xếp đệ quy và dễ quan sát bảng. Đổi lại, nó có thể tính những trạng thái mà câu hỏi cuối không cần.
Python
n = 8
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
print(dp)
print(dp[n])Kết quả
[0, 1, 1, 2, 3, 5, 8, 13, 21] 21
Ở đây n = 8, nên gán dp[1] an toàn. Nếu cho phép n = 0, cần kiểm tra trước khi gán chỉ số 1. Với mỗi cách và n = 1000, có tối đa 1001 trạng thái; số lần kết hợp là tuyến tính, chưa tính chi phí số nguyên lớn.
Khi chỉ cần kết quả cuối, Fibonacci chỉ cần hai giá trị trước. Gán đồng thời giữ giá trị cũ của cả hai biến trước khi cập nhật.
Python
n = 8
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
print(a)Kết quả
21
Sau mỗi vòng, a là Fibonacci tại chỉ số vừa đi tới và b là số kế tiếp. Chứng minh bằng cách kiểm tra cặp ban đầu rồi xét một lần cập nhật. Cách này giữ hai số thay vì cả bảng, nhưng không còn sẵn lịch sử để truy vết.
Chi phí nhỏ nhất phụ thuộc quy ước trả phí
Xét một cầu thang có n bậc đánh số từ 0. Bạn được bắt đầu tại bậc 0 hoặc bậc 1; từ đó mỗi lần đi lên 1 hoặc 2 vị trí. Phí cost[i] được trả khi rời bậc i; vị trí n là đích và không có phí.
Đặt dp[i] là phí nhỏ nhất khi đến vị trí i. Vì được chọn điểm bắt đầu, dp[0] = dp[1] = 0. Với i >= 2, vị trí trước đích là i-1 hoặc i-2, nên lấy nhỏ nhất của hai tổng tương ứng.
Mọi đường hợp lệ có đúng một vị trí ngay trước i. Nếu đoạn tới vị trí ấy chưa tối ưu, thay nó bằng đoạn rẻ hơn sẽ giảm phí cả đường. Do đó, xét hai đoạn tối ưu đủ để tìm chi phí tối ưu tới i.
Python
cost = [10, 15, 20, 4]
n = len(cost)
dp = [0] * (n + 1)
for i in range(2, n + 1):
dp[i] = min(dp[i - 1] + cost[i - 1],
dp[i - 2] + cost[i - 2])
print(dp)
print(dp[n])Kết quả
[0, 0, 10, 15, 19] 19
Với dữ liệu trên, bảng là 0, 0, 10, 15, 19. Bắt đầu ở bậc 1, đi sang bậc 3 rồi tới đích có phí 15 + 4 = 19. Một đường qua bậc 0 và bậc 2 có phí 30.
Ở vị trí 2, hai lựa chọn trả lần lượt 15 khi rời bậc 1 và 10 khi rời bậc 0. Vì vậy dp[2] = 10. Ở vị trí 3, so sánh 10 + 20 với 0 + 15, được dp[3] = 15.
Cuối cùng, tới vị trí 4 từ bậc 3 tốn 15 + 4, còn từ bậc 2 tốn 10 + 20. Giá trị 19 được chọn. Chú ý dp[i] không bao gồm phí rời vị trí i, vì tại thời điểm đó bạn mới đến nơi.
Nếu phí âm biểu diễn khoản được hoàn, cùng công thức vẫn hợp lệ. Đường chỉ đi lên, nên không thể quay lại một bậc âm vô hạn lần. Khi mọi phí đều dương, không thể suy luận rằng bắt đầu ở bậc rẻ hơn lập tức cho cả đường rẻ hơn; các bước sau cũng ảnh hưởng kết quả.
Mỗi vị trí xét hai ứng viên. Với n = 10000, có chưa tới 20000 ứng viên và n+1 ô. Thời gian là O(n), bộ nhớ là O(n); có thể giữ hai ô gần nhất nếu không cần truy vết.
Đổi tiền ít đồng nhất cần nhận diện tổng không thể tạo
Cho các mệnh giá nguyên dương, mỗi loại dùng không giới hạn. Đặt dp[x] là số đồng ít nhất tạo đúng tổng x. Với x = 0, không cần đồng nào nên dp[0] = 0.
Mỗi cách tạo tổng dương đều có một đồng cuối c. Phần còn lại phải tạo tổng x-c; nếu phần đó có cách dùng ít đồng hơn, thay vào sẽ cải thiện cả cách. Vì vậy, lấy nhỏ nhất của dp[x-c] + 1 qua các c <= x là đúng.
Dùng S + 1 làm dấu chưa thể tạo tổng khi tổng đích là S. Với mệnh giá dương, một cách hợp lệ không thể dùng quá S đồng. Không cộng từ dấu này vì nó không phải lời giải thật.
7 dòng
| Tổng | Số đồng ít nhất |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 2 |
| 3 | 1 |
| 4 | 1 |
| 5 | 2 |
| 6 | 2 |
Tổng 6 cần hai đồng 3. Lấy đồng lớn nhất trước sẽ chọn 4 rồi hai đồng 1, nên tham lam không đúng với mọi bộ mệnh giá. Với các đồng 4 và 6, tổng 5 không tạo được; dấu chưa đạt phải được chuyển thành kết quả riêng.
Đọc bảng từ tổng 0: tổng 1 dùng một đồng 1, tổng 2 dùng hai đồng 1, còn tổng 3 dùng một đồng 3. Tổng 4 dùng một đồng 4. Với tổng 5, có thể nối đồng 1 vào tổng 4, nên cần hai đồng.
Khi xét tổng 6, nối đồng 3 vào tổng 3 tạo ứng viên hai đồng. Nối đồng 4 vào tổng 2 tạo ứng viên ba đồng. Nối đồng 1 vào tổng 5 cũng tạo ba đồng. Giá trị nhỏ nhất là hai; cùng một đồng mệnh giá 3 được dùng hai lần theo đúng quy định không giới hạn.
Trường hợp S = 0 không đi qua vòng tính tổng dương và trả 0 ngay từ cơ sở. Nếu mọi mệnh giá lớn hơn một tổng dương, không có ứng viên hợp lệ cho tổng đó. Việc lặp lại mệnh giá trong đầu vào không đổi đáp án, dù làm tăng số lần xét.
Python
coins = [4, 6]
S = 5
inf = S + 1
dp = [inf] * (S + 1)
dp[0] = 0
for x in range(1, S + 1):
for c in coins:
if c <= x and dp[x - c] != inf:
dp[x] = min(dp[x], dp[x - c] + 1)
print(-1 if dp[S] == inf else dp[S])Kết quả
-1
Vì c dương nên x-c < x; duyệt x tăng bảo đảm ô cần đọc đã được xử lý. Với S = 10000 và 20 loại, có tối đa 200000 lần xét. Độ phức tạp là O(S * k) thời gian và O(S) bộ nhớ, với k là số loại đồng.
Python
coins = [4, 3, 1]
remaining = 6
used = []
for c in coins:
while remaining >= c:
remaining -= c
used.append(c)
print(used, len(used))
print([3, 3], 2)Kết quả
[4, 1, 1] 3 [3, 3] 2
Số trạng thái và số lựa chọn quyết định thời gian
Đếm số trạng thái có thể tính, rồi nhân với số lựa chọn tối đa cần xét ở mỗi trạng thái. Với cầu thang, có n+1 trạng thái và tối đa hai lựa chọn. Với đổi tiền, có S+1 trạng thái và tối đa k lựa chọn.
Không phải công thức nào cũng có cùng chi phí. Nếu mỗi chuyển tiếp duyệt một danh sách dài, không được gọi toàn bộ lời giải là tuyến tính chỉ vì bảng có một chiều. Cũng cần tính bộ nhớ của bảng và ngăn xếp đệ quy.
Python
coins = [1, 3, 4]
S = 6
checks = 0
for x in range(1, S + 1):
for c in coins:
checks += 1
print(checks)Kết quả
18
Đoạn này xét 18 cặp tổng và mệnh giá. Một số cặp bị bỏ qua sau điều kiện c <= x, nhưng vẫn được tính vào số lần kiểm tra. Đếm như vậy cho một giới hạn trên đơn giản và an toàn.
Lỗi thường gặp
| Lỗi | Vì sao sai | Cách sửa |
|---|---|---|
Đặt dp[0] = 0 khi đếm cách leo | Mất cách rỗng làm nền cho bước đầu. | Đặt dp[0] = 1 theo quy ước đề. |
| Nhầm phí khi đến và khi rời bậc | Công thức dùng sai chỉ số phí. | Viết quy ước trước rồi kiểm tra đường nhỏ. |
| Coi tổng chưa đạt có chi phí 0 | Trạng thái không hợp lệ tạo ra đáp án giả. | Dùng dấu chưa đạt và kiểm tra trước khi chuyển. |
| Duyệt trước ô mà công thức cần | Ô được đọc chưa chứa đáp án cuối. | Chọn thứ tự theo quan hệ phụ thuộc. |
| Dùng khóa ghi nhớ thiếu thông tin | Hai bài toán con khác nhau nhận chung kết quả. | Đưa đủ điều kiện ảnh hưởng vào trạng thái. |
Tóm tắt
DP lưu lời giải các trạng thái liên quan để tránh tính lặp. Hãy xác định ý nghĩa trạng thái, cơ sở, chuyển tiếp và thứ tự trước khi viết mã. Chứng minh các lựa chọn đủ và phân tích số trạng thái cùng chi phí mỗi lựa chọn.