Thuật Toán Tham Lam (Greedy)

1️⃣ Thuật toán tham lam là gì?

Thuật toán tham lam nghĩa là:

👉 Ở mỗi bước, mình luôn chọn thứ “tốt nhất ngay lúc này”. Không cần suy nghĩ quá xa, chỉ nhìn cái lợi trước mắt.

Tuy đơn giản, nhưng nhiều bài toán lại giải được rất nhanh nhờ cách này.

---

2️⃣ 🎒 Ví dụ đời thường: Thuật toán tham lam là gì?

Mẹ đưa cho các bạn 2 tờ tiền:

• Một tờ 100.000 đ
• Một tờ 200.000 đ

Và nói:

👉 “Các con chỉ được chọn 1 tờ!”

Vậy tụi em chọn tờ nào?

➡️ Tờ 200.000 đ

Vì nó có giá trị lớn hơn, dù:

• kích thước giống nhau
• hình dạng giống nhau
• số lượng đều là 1 tờ

🎯 Đây chính là cách suy nghĩ của thuật toán tham lam:

👉 Trong mọi lựa chọn, mình luôn chọn cái mang lại giá trị lớn nhất ngay lúc đó.

---

🧩 Liên hệ giải thuật tham lam

Trong lập trình:

• Mỗi bước ta chọn giá trị tốt nhất ngay lúc đó
• Và tiếp tục như vậy cho đến hết bài

Nếu tiêu chí đúng → ta sẽ có lời giải tối ưu.

---

3️⃣ Khi nào dùng được thuật toán tham lam?

Greedy chỉ đúng khi bài toán có 2 tính chất:

1. Lựa chọn tối ưu tại hiện tại → dẫn đến kết quả cuối cùng tốt nhất
2. Bài toán con giống bài toán lớn (optimal substructure)

❗ Nếu không có 2 tính chất này → dùng tham lam sẽ sai.

Given an integer n, count the total number of digits 1 appearing in all positive integers less than or equal to n.

Examples:

Input : n = 13 Output: 6 Explanation: Here, no <= 13 containing 1 are 1, 10, 11, 12, 13. So, total 1s are 6.

Input : n = 5 Output: 1 Explanation: Here, no <= 13 containing 1 is 1. So, the total 1s are 1..