Hướng dẫn giải của Đếm Tập Con Có Tổng K
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 0/1 Knapsack đếm số cách cổ điển.
Định nghĩa DP
Đặt ~dp[j]~ = số tập con của các phần tử đã xét có tổng đúng bằng ~j~.
Khởi tạo: ~dp[0] = 1~ (tập rỗng có tổng ~0~), ~dp[j] = 0~ với ~j > 0~.
Công thức chuyển trạng thái
Với mỗi phần tử ~a_i~, duyệt ~j~ từ ~K~ xuống ~a_i~: $$dp[j] = dp[j] + dp[j - a_i] \pmod{10^9+7}$$
Duyệt ngược để đảm bảo mỗi phần tử chỉ được chọn tối đa một lần (0/1).
Kết quả
~dp[K]~ sau khi xử lý tất cả phần tử.
Phân tích độ phức tạp
- Thời gian: ~O(N \times K)~
- Bộ nhớ: ~O(K)~ (dùng mảng 1 chiều tối ưu)
Ví dụ minh họa
Mảng ~[1, 2, 3]~, ~K = 3~:
| Bước | dp[0] | dp[1] | dp[2] | dp[3] |
|---|---|---|---|---|
| Khởi tạo | 1 | 0 | 0 | 0 |
| Thêm 1 | 1 | 1 | 0 | 0 |
| Thêm 2 | 1 | 1 | 1 | 1 |
| Thêm 3 | 1 | 1 | 1 | 2 |
Kết quả: ~dp[3] = 2~, là ~\{3\}~ và ~\{1,2\}~.
Bình luận