贪心

字数统计: 2.7k字 | 阅读时长: 9分

2020-09-28

摘要: 本文系统梳理了贪心相关的算法。并汇总了 leetcode 上的相关的题目。

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

正确性证明(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 区间类 : 区间问题汇总

区间不相交选择(活动安排问题)

区间图着色问题

253. 会议室 II

区间选点

区间覆盖

1.2 峰谷类 : 峰谷类问题分类汇总

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

1
2
3

因为交易不限次数，每个谷都应该对应一个最近的峰

微扰法证明

714. 买卖股票的最佳时机含手续费

122. 买卖股票的最佳时机 II 中没有手续费的做法：$\sum\limits_{i}(peak_{i}-valley_{i})$

本题含手续费的做法：$\sum\limits_{i}(peak_{i}-valley_{i})$，相当于把峰降低，如果降低之后还是峰，那就是真的峰。

135. 分发糖果

1 2	关键的是谷，谷的糖果数量一定是 1 对每个位置，找左右距离最近的谷

376. 摆动序列

1 2	最长摆动序列一定以 nums[0] 开头，以 nums[n-1] 结尾(需要证明) 最长摆动序列除了首尾两个点外，是由交替的峰谷组成