贪心

💡 想象一下，你面前有一堆不同面额的硬币（比如 1 元、5 角、1 角），你需要用最少数量的硬币凑出 1.8 元。
一个很自然的想法是：每次都先拿面额最大的硬币。

先拿 1 元，剩下 0.8 元；再拿 5 角，剩下 0.3 元；最后拿三个 1 角。

整个过程，我们在每一步都做出了 当前看来最好的选择__，这就是贪心算法的核心思想。

相较于动态规划，贪心算法的使用条件更加苛刻，其主要关注问题的两个性质：

• 贪心选择性质：只有当局部最优选择始终可以导致全局最优解时，贪心算法才能保证得到最优解。
• 最优子结构：原问题的最优解包含子问题的最优解。