贪心算法

贪心算法

• 贪心算法：
  • 在每一步选择中都采取当前状态下的最优决策（局部最优）。
  • 并希望由此导致的最终结果是全局最优。
• 贪心算法与一般的搜索，以及动态规划相比，不同之处在于：它不对整个状态空间进行遍历或计算，而是始终按照局部最优选择执行下去，不再回头。
• 因为这个特性，贪心算法不一定能得到正确的结果，除非可以证明，按照适当的方法做出局部最优选择，依然可以得到全局最优结果。
• 能用贪心算法求解的题目，也都可以用搜索或动态规划求解，但贪心算法一般是最高效的。
• 遇到题目，先想搜索、动态规划等基于全局的解法，若时间复杂度太高，再考虑贪心。

---

LeetCode 练习题

• 860. 柠檬水找零
• 455. 分发饼干
• 122. 买卖股票的最佳时机 II
• 45. 跳跃游戏 II

---