贪心 Greedy wiki

贪⼼法，⼜称贪心算法、贪婪算法：在对问题求解时，总是做出在当前看来是最好的选择。

适⽤ Greedy 的场景

简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。这种⼦问题最优解称为最优子结构。

贪⼼算法与动态规划的不同在于它对每个⼦问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。

相关题目：

122. 买卖股票的最佳时机 II

860. 柠檬水找零

455. 分发饼干

874. 模拟行走机器人