Hiểu sự khác biệt giữa greedy algorithm và dynamic programming.
Greedy algorithm
Xây dựng giải pháp từng phần, từng bước. Bước tiếp theo chọn lợi ích rõ ràng, ngay lập tức nhất.
- Bài toán chọn giá trị tối ưu cục bộ dẫn đến tối ưu toàn cục → phù hợp greedy.
- Không đảm bảo greedy dẫn đến giải pháp tối ưu.
- Lựa chọn tối ưu cục bộ tại mỗi giai đoạn.
- Hiệu quả bộ nhớ (không cần quay lại thay đổi).
- Nhanh hơn dynamic programming.
- Ví dụ: Dijkstra shortest path O(ELogV + VLogV).
- Giải pháp tính toán tiến (forward), không quay lại giá trị trước.
Dynamic Programming
Kỹ thuật tối ưu lưu kết quả sub-problem để không tính lại khi cần. Giảm độ phức tạp từ exponential sang polynomial.
- Ví dụ: đệ quy → DP bằng cách lưu kết quả.
- Quyết định mỗi bước xem xét bài toán hiện tại và giải pháp sub-problem đã giải → tính tối ưu.
- Đảm bảo giải pháp DP là tối ưu.
- Chọn giải pháp tối ưu toàn cục, dùng công thức lưu state trước.
- Cần bảng DP để memoization → tăng memory complexity.
- Chậm hơn greedy.
- Ví dụ: Bellman Ford O(VE).
- Xác định giải pháp bottom-up hoặc top-down, xây từ bài toán nhỏ đã tối ưu.