Hướng dẫn giải của Phân Hoạch Bằng Nhau
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
Quan sát: Nếu tổng mảng là ~S~, ta cần tìm tập con có tổng đúng bằng ~S/2~.
Điều kiện cần: ~S~ phải là số chẵn. Nếu lẻ → trả lời NO ngay.
Định nghĩa DP
Đặt ~dp[j]~ = true nếu tồn tại tập con có tổng ~j~, false ngược lại.
Khởi tạo: ~dp[0] = \text{true}~.
Công thức chuyển trạng thái
Với mỗi phần tử ~a_i~, duyệt ~j~ từ ~S/2~ xuống ~a_i~: $$dp[j] = dp[j] \lor dp[j - a_i]$$
Kết quả
Trả lời YES nếu ~dp[S/2] = \text{true}~, ngược lại NO.
Độ phức tạp
- Thời gian: ~O(N \times S)~ trong đó ~S = \sum a_i~
- Bộ nhớ: ~O(S)~
Bình luận