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