说明
贪心的正确性证明方法这块完全参考《算法竞赛进阶指南》0x07
问题模型，维护贪心的算法或数据结构，疑难杂症里面全都是力扣上的题目链接。
相当于从问题模型、算法和数据结构这两个维度给贪心的问题建了一个二级索引，不好分类的题目放到了疑难杂症里。
目录
- 正确性证明(参考: 《算法竞赛进阶指南》0x07)
- 微扰法
- 范围缩放
- 决策包容性
- 反证法
- 数学归纳法
- 问题模型
- 区间类
- 区间不相交选择
- 区间选点
- 区间图染色
- 区间覆盖
- 峰谷类
- 逆向思维
- 加油站问题
- 最小生成树
- 单源最短路径
- 哈夫曼树
- 部分背包
- 多指标规划
- 删数,选数,拼数,改数
- 子序列匹配
- 分拆
- 子串分拆
- 子序列分拆
- 重排问题与置换群
- 田忌赛马
- 情侣牵手
- ...
- 构造问题
- 装箱问题
- 区间类
- 维护贪心的算法或数据结构
- 排序
- 栈
- 堆
- 平衡树
- 双指针
- 二分
- 链表
- 疑难杂症
$0 正确性证明
参考：《算法竞赛进阶指南》0x07小节
贪心是一种在每次决策时采取当前以以下最优的策略的算法，贪心算法要求问题全局最优性可以由局部最优性导出。
这种全局最优性可以由局部最优性导出需要证明，常见的证明手段如下：
微扰法
证明在任意状态下，任何对局部最优策略的微小改变都会造成整体结果变差。这种方法在排序贪心的正确性证明中常用。
范围缩放
证明任何对局部最优策略作用范围的扩展都不会造成整体结果变差。
决策包容性
证明在任意状态下，做出局部最优策略之后，在问题状态空间中的可达集合包含了作出其它任何决策后的可达集合。即：这个局部最优策略提供的可能性包含其它所有策略提供的可能性。
当前位置 i，下一步的选择范围 [i+1..i+nums[i]]
选择其中的 1 <= k <= nums[i] 使得下一步能到达的范围最远，max(i + k + nums[i + k])p=str1*str2*...*strm
在s中依次找到最左边的str1,str2,...,strm，只要能在s耗尽前都找到，就可以匹配反证法
数学归纳法
$1 问题模型
1.1 区间类 :
区间不相交选择(活动安排问题)
区间图着色问题
区间选点
区间覆盖
1.2 峰谷类
1.3 逆向思维
1.4 加油站问题
1.5 最小生成树
1.6 单源最短路径
1.7 哈夫曼树
1.8 部分背包问题
1.9 多指标规划
择优型
淘汰型
1.10 删数拼数选数改数
删数(选数)问题
拼数问题
改数问题
1.11 子序列匹配
1.12 分拆问题
子集分拆
子序列分拆
子串分拆
1.13 重排问题与置换群
使得相邻 k 个元素不同
使得权值最大
田忌赛马
情侣牵手
1.14 构造问题
- 984. 不含 AAA 或 BBB 的字符串
- 1405. 最长快乐字符串
- 484. 寻找排列
- 651. 4键键盘
- 995. K 连续位的最小翻转次数
- 1046. 最后一块石头的重量
- 1253. 重构 2 行二进制矩阵
- 1605. 给定行和列的和求可行矩阵
- 1354. 多次求和构造目标数组
- 1505. 最多 K 次交换相邻数位后得到的最小整数
- 1536. 排布二进制网格的最少交换次数
- 1460. 通过翻转子数组使两个数组相等
- 1144. 递减元素使数组呈锯齿状
- 1558. 得到目标数组的最少函数调用次数
- 1585. 检查字符串是否可以通过排序子字符串得到另一个字符串
1.15 装箱问题
$2 维护贪心策略的算法或数据结构
2.1 排序
区间问题
其它 :
- 406. 根据身高重建队列
- 179. 最大数
- 524. 通过删除字母匹配到字典里最长单词
- 948. 令牌放置
- 1029. 两地调度
- 1058. 最小化舍入误差以满足目标
- 1090. 受标签影响的最大值
- 1403. 非递增顺序的最小子序列
2.2 栈
删数，拼数，选数问题
括号
其它
2.3 堆
加油站问题
哈夫曼树问题
构造性问题
重排问题
多指标规划问题
2.4 平衡树
重排问题
分拆问题
区间问题
其它
2.5 双指针
子序列匹配问题
乘船问题
最小极差
其它
2.6 二分
子序列匹配问题
2.7 链表
2.8 位掩码
$3 疑难杂症
评论 (6)
