正确性证明(Ref: 《算法竞赛进阶指南》)
微扰法范围缩放决策包容性反证法数学归纳法 问题模型
区间类
区间不相交选择区间选点区间图染色区间覆盖 峰谷类逆向思维加油站问题最小生成树单源最短路径哈夫曼树部分背包多指标规划删数,选数,拼数,改数子序列匹配分拆
子串分拆子序列分拆 重排问题与置换群
田忌赛马情侣牵手… 构造问题装箱问题调度问题拟阵 维护贪心的算法或数据结构
排序,
自定义排序栈堆平衡树双指针二分链表 疑难杂症
$0 正确性证明
参考：《算法竞赛进阶指南》0x07小节
贪心是一种在每次决策时采取当前以以下最优的策略的算法，贪心算法要求问题全局最优性可以由局部最优性导出。
这种全局最优性可以由局部最优性导出需要证明，常见的证明手段如下：
微扰法
证明在任意状态下，任何对局部最优策略的微小改变都会造成整体结果变差。这种方法在排序贪心的正确性证明中常用。
122. 买卖股票的最佳时机 II
范围缩放
证明任何对局部最优策略作用范围的扩展都不会造成整体结果变差。
决策包容性
证明在任意状态下，做出局部最优策略之后，在问题状态空间中的可达集合包含了作出其它任何决策后的可达集合。即：这个局部最优策略提供的可能性包含其它所有策略提供的可能性。
45. 跳跃游戏 II / 55. 跳跃游戏
当前位置 i，下一步的选择范围 [i+1..i+nums[i]]
选择其中的 1 <= k <= nums[i] 使得下一步能到达的范围最远，max(i + k + nums[i + k])
类似区间覆盖的思想
44. 通配符匹配
p=str1*str2*...*strm
在s中依次找到最左边的str1,str2,...,strm，只要能在s耗尽前都找到，就可以匹配
有点类似kmp的思想
反证法
134. 加油站
数学归纳法
$1 问题模型
1.1 区间类 : 区间问题汇总
区间不相交选择(活动安排问题)
435. 无重叠区间759. 员工空闲时间1353. 最多可以参加的会议数目1520. 最多的不重叠子字符串
区间图着色问题
253. 会议室 II
区间选点
452. 用最少数量的箭引爆气球757. 设置交集大小至少为2
区间覆盖
45. 跳跃游戏 II / 55. 跳跃游戏763. 划分字母区间330. 按要求补齐数组1024. 视频拼接1326. 灌溉花园的最少水龙头数目
1.2 峰谷类 : 峰谷类问题分类汇总
122. 买卖股票的最佳时机 II
因为交易不限次数，每个谷都应该对应一个最近的峰
微扰法证明
714. 买卖股票的最佳时机含手续费
122. 买卖股票的最佳时机 II 中没有手续费的做法：
∑
i
(
p
e
a
k
i
−
v
a
l
l
e
y
i
)
\sum\limits_{i}(peak_{i}-valley_{i})
i∑(peaki−valleyi)
本题含手续费的做法：
∑
i
(
p
e
a
k
i
−
v
a
l
l
e
y
i
)
\sum\limits_{i}(peak_{i}-valley_{i})
i∑(peaki−valleyi)，相当于把峰降低，如果降低之后还是峰，那就是真的峰。
135. 分发糖果
关键的是谷，谷的糖果数量一定是 1
对每个位置，找左右距离最近的谷
376. 摆动序列
最长摆动序列一定以 nums[0] 开头，以 nums[n-1] 结尾(需要证明)
最长摆动序列除了首尾两个点外，是由交替的峰谷组成
1.3 逆向思维
991. 坏了的计算器936. 戳印序列1591. 奇怪的打印机 II1354. 多次求和构造目标数组1558. 得到目标数组的最少函数调用次数
1.4 加油站问题 : 贪心-加油站问题
134. 加油站871. 最低加油次数
1.5 最小生成树
1.6 单源最短路径
1.7 哈夫曼树 ： 贪心-哈夫曼编码
1167. 连接棒材的最低费用
1.8 部分背包问题 ：贪心-部分背包问题
1196. 最多可以买到的苹果数量1414. 和为 K 的最少斐波那契数字数目
1.9 多指标规划 : 贪心-双指标规划问题
502. IPO857. 雇佣 K 名工人的最低成本1383. 最大的团队表现值630. 课程表 III
1.10 删数拼数选数改数 : 贪心-删数,拼数,选数,改数
316. 去除重复字母 / 1081. 不同字符的最小子序列402. 移掉K位数字321. 拼接最大数738. 单调递增的数字861. 翻转矩阵后的得分955. 删列造序 II944. 删列造序1005. K 次取反后最大化的数组和1053. 交换一次的先前排列1509. 三次操作后最大值与最小值的最小差
1.11 子序列匹配
392. 判断子序列44. 通配符匹配1055. 形成字符串的最短路径792. 匹配子序列的单词数
1.12 分拆问题 : 贪心-分拆问题
子集分拆
846. 一手顺子1296. 划分数组为连续数字的集合
子序列分拆
1121. 将数组分成几个递增序列659. 分割数组为连续子序列
子串分拆
1221. 分割平衡字符串
1.13 重排问题与置换群 ： 贪心-重排问题
358. K 距离间隔重排字符串621. 任务调度器767. 重构字符串870. 优势洗牌1433. 检查一个字符串是否可以打破另一个字符串455. 分发饼干765. 情侣牵手1589. 所有排列中的最大和
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 装箱问题 : 装箱问题
1564. Put Boxes Into the Warehouse I1580. Put Boxes Into the Warehouse II
1.16 调度问题
1.17 拟阵
$2 维护贪心策略的算法或数据结构
2.1 排序
自定义排序
区间问题
253. 会议室 II763. 划分字母区间452. 用最少数量的箭引爆气球435. 无重叠区间
其它 : 自定义排序
406. 根据身高重建队列179. 最大数524. 通过删除字母匹配到字典里最长单词948. 令牌放置1029. 两地调度1058. 最小化舍入误差以满足目标1090. 受标签影响的最大值1403. 非递增顺序的最小子序列
2.2 栈
删数，拼数，选数问题
316. 去除重复字母 / 1081. 不同字符的最小子序列402. 移掉K位数字321. 拼接最大数738. 单调递增的数字
括号
1111. 有效括号的嵌套深度
其它
649. Dota2 参议院
2.3 堆
加油站问题
871. 最低加油次数
哈夫曼树问题
1167. 连接棒材的最低费用
构造性问题
1354. 多次求和构造目标数组
重排问题
358. K 距离间隔重排字符串621. 任务调度器 (可以优化为数学法维护)767. 重构字符串
多指标规划问题
502. IPO857. 雇佣 K 名工人的最低成本1383. 最大的团队表现值630. 课程表 III
2.4 平衡树
重排问题
870. 优势洗牌
分拆问题
455. 分发饼干846. 一手顺子
区间问题
759. 员工空闲时间
其它
1046. 最后一块石头的重量
2.5 双指针
子序列匹配问题
44. 通配符匹配 (可以优化为AC自动机维护)
乘船问题
881. 救生艇
最小极差
910. 最小差值 II
其它
948. 令牌放置
2.6 二分
子序列匹配问题
392. 判断子序列1055. 形成字符串的最短路径792. 匹配子序列的单词数
2.7 链表
1388. 3n 块披萨 类似网络流中的增广路做法
2.8 位掩码
1386. 安排电影院座位
$3 疑难杂症 : 贪心-疑难杂症
406. 根据身高重建队列860. 柠檬水找零649. Dota2 参议院881. 救生艇910. 最小差值 II927. 三等分948. 令牌放置1007. 行相等的最少多米诺旋转1029. 两地调度1247. 交换字符使得字符串相同1338. 数组大小减半1386. 安排电影院座位1400. 构造 K 个回文字符串1403. 非递增顺序的最小子序列1578. 避免重复字母的最小删除成本1567. 乘积为正数的最长子数组长度
