学习笔记N-035
贪心
- 更新
- 内容块
- 32
- 阅读
- 约 1 分钟
- 路径
- 学习笔记 / C++ / C++算法
包括贪心，以及之后的算法，无一不在强调状态和状态转移
集合选择问题
状态：已选空间的集合
初始状态：空集合
目标状态：无法再选择
最优方案：最大集合
状态转移：选择一个不重叠的区间
策略：按右端点排序后，仅根据已选择的右端点选择第一个不重叠的区间
顺序无关，尝试 sort
区间：左右端点，中点，长度，组合
不断尝试，找反例
集合选择：剩余区间包含其他剩余区间
截止日期问题
状态：第 i 天
初始状态：最后一天
目标状态：第一天
最优方案：最大收益
状态转移：选择在截止日期内的任务
策略：仅根据当前日期，选收益最大的
n 个有序数组
