贪心算法
一、概念
基本思想:贪心算法并不从整体最优上加以考虑,它所做的选择只是在某种意义上的局部最优解。 基本要素:最优子结构性质和贪心选择性质。
二、训练122. 买卖股票的最佳时机 II
392. 判断子序列
455. 分发饼干
860. 柠檬水找零
- 主要体现在:需要找15元时,优先找10+5,其次再选取5+5+5组合。每一步都做此“贪心选择”,并最终达到“全局最优解”。
1221. 分割平衡字符串