Khi gặp một bài toán mới, đừng vội code ngay. Hãy theo quy trình dưới đây để tránh mất thời gian vào hướng sai.
Quy trình 5 bước
Bước 1: Đọc kỹ đề
- Đọc toàn bộ đề ít nhất hai lần.
- Gạch chân các từ khóa quan trọng: "lớn nhất", "nhỏ nhất", "đúng một lần", "liên tiếp"...
- Xác định rõ: Input là gì? Output là gì?
- Đọc kỹ ràng buộc (, giá trị các phần tử, số test case).
Bước 2: Thử ví dụ mẫu bằng tay
Trước khi nghĩ thuật toán, hãy tự giải bằng tay các ví dụ trong đề. Điều này giúp bạn:
- Hiểu đúng yêu cầu bài.
- Phát hiện các trường hợp đặc biệt sớm.
- Có trực giác về hướng giải.
Bước 3: Xác định độ phức tạp cần thiết
Từ ràng buộc , xác định thuật toán cần có độ phức tạp gì:
| Độ phức tạp | |
|---|---|
| được | |
| Cần hoặc | |
| Cần hoặc |
Bước 4: Nghĩ thuật toán
Xem xét từng hướng từ đơn giản đến phức tạp:
- Brute force có được không? (thường hoặc )
- Có thể sắp xếp để đơn giản hóa không?
- Có thể dùng tìm kiếm nhị phân trên đáp án không?
- Có cấu trúc con tối ưu → thử DP?
- Có lựa chọn tham lam rõ ràng → thử Greedy?
- Bài toán liên quan đến đồ thị → BFS/DFS/Dijkstra...?
Bước 5: Cài đặt và kiểm tra
- Code từng phần nhỏ, kiểm tra từng bước.
- Test với ví dụ trong đề trước.
- Tự tạo thêm test case: trường hợp nhỏ nhất (), lớn nhất (), trường hợp đặc biệt.
Kỹ thuật: Simplify the Problem
Nếu bài quá khó, hãy đơn giản hóa trước:
- Giả sử nhỏ (chỉ 5-10 phần tử) — giải brute force.
- Bỏ bớt ràng buộc — giải phiên bản dễ hơn.
- Giải bài 1D trước khi nghĩ đến 2D.
Sau khi hiểu bài đơn giản hơn, dần dần mở rộng lên bài gốc.
Kỹ thuật: Think Backwards
Với một số bài, suy nghĩ ngược lại (từ đáp án về đầu vào) dễ hơn:
- Bài xóa phần tử → thêm phần tử theo thứ tự ngược.
- Bài đồ thị tách → đồ thị gộp (DSU).
Các tín hiệu nhận biết thuật toán
| Từ khóa trong đề | Hướng giải |
|---|---|
| "Đường đi ngắn nhất" | BFS (không trọng số), Dijkstra (trọng số dương) |
| "Tổng lớn nhất / nhỏ nhất trên đoạn" | Prefix sum, Segment Tree |
| "Số lần xuất hiện" | Hash map |
| "Dãy con tăng dài nhất" | DP — LIS |
| "Kết nối / cùng nhóm" | DSU |
| "Tất cả tập con" | Bitmask DP |
| "In ra có / không" | Thường là DP hoặc Greedy |
| "K nhỏ nhất / lớn nhất" | Heap / Binary search |
Bình luận