在每一個步驟中選擇當下最好的選項
實例講解 - 找零錢
目前有的硬幣面額為 25、10、5、1，要找41元且優先使用面額最大的硬幣
| 回合數 | 當下要找的零錢 | 當下使用的最大面額 | 剩餘要找的零錢 |
|---|---|---|---|
| 1 | 41 | 25 | 16 |
| 2 | 16 | 10 | 6 |
| 3 | 6 | 5 | 1 |
| 4 | 1 | 1 | 0 |
總共需要四回，總共需要1枚25元、1枚10元、1枚5元、1枚1元
貪心演算法的使用時機
需要同時符合以下條件
1. 每次的選擇互相獨立，互不影響
每一步的局部的選擇結果不會影響後續的選擇
2. 找最優解
把大問題拆分成若干性質的小問題，每個小問題的最優解組合起來就是大問題的最優解
跟 動態規劃的差別
動態規劃的核心思路跟貪心演算法類似，都是把大問題拆分成若干性質相似的小問題，從小問題的答案推導出大問題的答案
但是跟動態規劃的最大差別是，紀錄所有小問題的答案以確保最後取得大問題的最優答案
而貪心演算法的最後答案不一定是最好的答案