Lập trình 22/09/2026 5 phút

Tham lam vs lười trong regex: vì sao .* nuốt cả chuỗi còn .*? thì không

Cùng một mẫu, chỉ thêm một dấu ?, mà kết quả khác hẳn — và tốc độ cũng vậy. Bài này đo thật bằng python re: greedy .* nuốt cả '<b>xin</b> và <i>bạn</i>' thành một match, lazy .*? tách đúng bốn thẻ; và trên input 200k ký tự, greedy chậm hơn lazy 785 lần vì phải nhả dần (backtrack). Hiểu cơ chế để chọn đúng và tránh lỗi trích sai.

Lập trình 22/09/2026 7 phút

Tham lam hay quy hoạch động: khi chọn 'tốt nhất ngay bây giờ' lại cho kết quả tệ nhất

Thuật toán tham lam (greedy) chọn phương án tốt nhất ở mỗi bước — nhanh và đơn giản. Nhưng nó chỉ đúng với một số bài toán. Bài này đo thật trong go-lab bài đổi tiền: với bộ mệnh giá 1,5,10,25 greedy cho lời giải tối ưu, nhưng với bộ 1,7,10 để đổi 14 đồng greedy dùng 5 đồng trong khi DP chỉ cần 2. Greedy nhanh hơn DP 9-93 lần nhưng có thể sai; DP luôn đúng nhưng tốn hơn.