Hướng dẫn giải của Số Cách Đổi Tiền
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Tác giả:
Ý tưởng chính
Đây là bài toán Unbounded Knapsack (mỗi xu dùng không giới hạn lần) đếm số cách.
Định nghĩa DP
Đặt ~dp[j]~ = số cách tạo tổng đúng bằng ~j~ từ các xu đã xét.
Khởi tạo: ~dp[0] = 1~, ~dp[j] = 0~ với ~j > 0~.
Công thức chuyển trạng thái
Với mỗi xu có mệnh giá ~c~, duyệt ~j~ từ ~c~ lên đến ~S~ (duyệt xuôi): $$dp[j] = dp[j] + dp[j - c] \pmod{10^9+7}$$
Chú ý quan trọng: Duyệt xuôi (từ nhỏ đến lớn) để cho phép dùng cùng một xu nhiều lần. Nếu duyệt ngược sẽ là bài 0/1 Knapsack.
Phân tích độ phức tạp
- Thời gian: ~O(N \times S)~
- Bộ nhớ: ~O(S)~
So sánh 0/1 và Unbounded
| 0/1 Knapsack | Unbounded Knapsack | |
|---|---|---|
| Mỗi item | Dùng tối đa 1 lần | Dùng không giới hạn |
| Duyệt j | Từ lớn về nhỏ | Từ nhỏ lên lớn |
Bình luận