第四章：动态规划。本章不会包含很多具体的算法，因为动态规划本身就是一种思想，没有固定模板或流程，不同题目的思路区别很大，而且代码很短很简单很短，都是一些简单的循环，重要的是构造思路，所以这里挑选一些经典例题作为讲解，以及介绍几种不同的常见的的动态规划方式或模型。DP有很多模型，例如线性DP，区间DP，状态压缩DP，计数DP等，但是面试笔试时不会都涉及，这里先暂时讲解背包问题和线性DP，区间DP三个模型。
动态规划就是一种利用已经算出来的子问题的答案来解决大问题，也就是将大问题拆分成小问题。动态规划的思想类似于递归的原理，区别就是动态规划是用循环实现的。
在处理动态规划问题的时候一般需要解决两个问题：
状态表示
数组中的每个元素表示的集合是什么
数组中的元素的每个值代表什么
状态计算
如何通过之前的状态得到下一个状态，即如何得出状态转移方程
背包问题
背包问题是最经典的动态规划问题，其中背包问题也分为很多种类，以下分别介绍一些基本背包问题
1. 01背包问题
有n个物品，每件物品的体积是vi，价值为wi。有一个容积为V的背包，现在需要在这n个物品中选择一些物品装入背包，使得背包内的物品总价值最大，并且体积之和不超过背包容积，每件物品只有一个，输出背包能容纳的最大价值。
分析思路：
整个问题总共涉及两个变量，选择的物品和使用的容积，因此使用一个二维数组
f[N][N]存储所有状态，f[i][j]表示在只使用前 i 个物品的条件下，使用的容积不超过 j，所能装下的最大价值。这里f[i][j]表示的集合是满足限制的所有的物品选择集合，值表示的是这些组合中的价值最大的值。关于如何计算状态，考虑f[i][j]表示的所有物品组合，可以分为两大类，一类是有第 i 件物品的组合，另一类是没有第 i 件物品的组合，在第一类物品选择中，相当于所有组合都不选第 i 件物品，而最大容量还是 j，这些组合的最大价值就是f[i - 1][j]；而对于第二类，这些组合中都含有第 i 件物品，可以将所有这些组合中的第 i 件物品全部去掉，那么这些组合的相对大小还是不变的，这些组合的最大价值就是f[i - 1][j - v[i]] + w[i]。因此可以设计一个两重循环来使用这个状态转移方程不断更新数组，最终答案就是f[n][V]；优化思路：考虑优化思路，对于每个
f[i][j]，其值只与f[i - 1][j]和f[i - 1][j - v[i]]，与第0 ~ i - 2次循环的值无关，因此可以考虑使用一个一维滚动数组f[]来实现。其中f[i]表示在使用容量不超过i时候背包所能装下的最大价值。至于 i 下标，则在 i 循环中自动递增，则现在的状态转移方程为f[j] = max(f[j], f[j - v[i]] + w[i])。
代码实现
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, V;
int v[N], w[N];
int f[N];
int main() {
cin >> n >> V;
for (int i = 0; i < n; i ++) cin >> v[i] >> w[i];
// DP过程
for (int i = 0; i < n; i ++)
for (int j = V; j >= v[i]; j --)
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[V] << endl;
return 0;
}需要说明的是：在循环中可以看到内部循环是从大到小循环的，这个是不能改变的。如果从小到大遍历，那么当更新f[j]时f[j - v[i]]必定已经被更新过了，那么此时f[j - v[i]]实际上是初版DP中的f[i][j - v[i]]，这个是错误的，因为f[i][j - v[i]]表示已经选择了第i件物品，不能继续选择了，因此从大到小遍历能保证遍历到f[j]时f[j - v[i]]还是上一轮的值。
2.完全背包问题
现在有n件物品，每件物品的体积是vi，价值是wi，现在有一个容量为V的背包，需要选择合适的物品放入背包，在总体积不超过背包容量的前提下总价值最大，输入最大值。每种物品有无限个。
分析思路：本题和01背包问题非常类似，区别就在于每种物品的个数，分析过程也相似
对于01背包中的状态转移方程
f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i])，对应在完全背包问题中的状态转移方程应该是f[i][j] = max(f[i - 1][j - k * v[i]] + k * w[i]), k <= j / v[i]。每一轮循环的实际意义就是对于第 i 个物品，判断在每种容量条件下加入这个物品会不会更优，每次更新都意味着选择一个该物品可以让总价值更大，更新的次数越多，第 i 件物品在最优组合中出现的次数也就越多。优化：优化也和01背包类似，不同的是这次内层循环可以从小到大遍历了，因为在初版状态转移方程中使用的是第i轮计算得到的值。
代码实现
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, V;
int v[N], w[N];
int f[N];
int main() {
cin >> n >> V;
for (int i = 0; i < n; i ++) cin >> v[i] >> w[i];
for (int i = 0; i < n; i ++)
for (int j = v[i]; j <= V; j ++)
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[V] << endl;
return 0;
}3.多重背包问题
现在有n件物品，每件物品的体积是vi，价值是wi，现在有一个容量为V的背包，需要选择合适的物品放入背包，在总体积不超过背包容量的前提下总价值最大，输入最大值。每种物品有si个。
分析思路：和前面两个背包问题类似，但是每种物品是有限个。状态转移方程实际上和完全背包问题是相同的：f[i][j] = max(f[i - 1][j - k * v[i]] + k * w[i])，0 <= k <= min(si，j / v[i])。
初版代码实现
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2500;
int n, V;
int v[N], w[N], s[N];
int f[N][N];
int main() {
cin >> n >> V;
for (int i = 1; i <= n ;i ++) cin >> v[i] >> w[i] >> s[i];
// 这里下标从1开始是因为每轮循环需要用到i - 1轮循环的值，防止数组越界
for (int i = 1; i <= n; i ++)
for (int j = v[i]; j <= V; j ++)
for (int k = 0; k * v[i] <= j && k <= s[i]; k ++)
f[i][j] = max(f[i - 1][j], f[i - 1][j - k * v[i]] + k * w[i]);
cout << f[n][V] << endl;
return 0;
}时间复杂度优化：初版代码的时间复杂度显然是O(nVk)，数据量稍微大一些，例如1000就可能超时。因此需要对算法进行优化。考虑将每种物品分组，假设第i件物品有s个，将其分为若干组，使得可以通过不同组组合来获得任意数量的第i件物品，可以将s个第i件物品分为1，2，4，8………2k，c个，其中c满足使得所有组加起来刚好是s个，可以证明这么划分是可以组合出来0 - s个第i件物品的，然后将每组物品分别看作一个物品，将其价值和体积存入v和w数组中，这样就可以将一个多重背包问题转换为01背包问题。
代码实现
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 25000;
// cur指针存放下面一组物品应该放到数组的哪个位置
int n, V, cur = 0;
int v[N], w[N];
int f[N];
int main() {
cin >> n >> V;
for (int i = 0; i < n; i ++) {
int a, b, c, k = 1;
cin >> a >> b >> c;
while (c >= k) {
v[cur] = k * a;
w[cur] = k * b;
cur ++;
c -= k;
k *= 2;
}
// 将剩余的物品也添加到数组中
if (c) {
v[cur] = c * a;
w[cur] = c * b;
cur ++;
}
}
// 这里需要注意物品不是n个了，是cur个
for (int i = 0; i < cur; i ++)
for (int j = V; j >= v[i]; j --)
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[V] << endl;
return 0;
}时间复杂度分析：由于每件物品都拆分成了log s组，最后转化成的01背包中共有n log s种物品，总的时间复杂度为O(nVlog s)。
4.分组背包问题
现在有n组物品，每组物品有si个不同的的物品，每个物品的价值分别是vij，wij，有一个容量为V的背包，现在要从所有物品中挑选一些放入背包，在总体积不超过背包容量的前提下使背包内物品的总价值最大，求出最大价值。每组物品最多选择一个。
分析思路：状态表示同01背包，状态方程变为f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i][k]] + w[i][k])。根据这个方程我们便可以写出一个初版动态规划代码。
初版代码实现
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, V;
int v[N][N], w[N][N], s[N];
int f[N][N];
int main() {
cin >> n >> V;
for (int i = 1; i <= n; i ++) {
cin >> s[i];
for (int j = 0; j < s[i]; j ++)
cin >> v[i][j] >> w[i][j];
}
for (int i = 1; i <= n; i ++)
for (int j = 0; j <= V; j ++) {
f[i][j] = f[i - 1][j];
for (int k = 0; k < s[i]; k ++)
if (j >= v[i][k])f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i][k]] + w[i][k]);
}
cout << f[n][V] << endl;
return 0;
}优化：优化空间和01背包类似，将数组变成一维的滚动数组
优化代码实现
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1000;
int n, V;
int v[N][N], w[N][N], s[N];
int f[N];
int main() {
cin >> n >> V;
for (int i = 1; i <= n; i ++) {
cin >> s[i];
for (int j = 0; j < s[i]; j ++)
cin >> v[i][j] >> w[i][j];
}
// 因为在原状态转移方程中使用的是i - 1轮循环的值，所以j还是从大到小遍历
for (int i = 1; i <= n; i ++)
for (int j = V; j >= 0; j --)
for (int k = 0; k < s[i]; k ++)
if (j >= v[i][k]) f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
cout << f[V] << endl;
return 0;
}线性DP
线性DP就是每个状态之间的关系是线性的，状态转移方程是简单的线性关系。
线性DP最经典的一个问题就是数字三角形问题。
数字三角形
给定一个数字三角形，从顶部出发，在每一节点可以选择向其左下方的节点或右下方的节点移动，一直走到最底层，要求找到一条路径，使得路径上的数字之和最大。
数字三角形示例： 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
分析思路：对每个元素进行定位，每一行的第一个元素为第一列的元素，第二个元素为第二个的元素。例如示例中的第三行的1坐标就为3，2。f[i][j]表示的集合是从起点开始，到达第 i 行第j列所有路径的集合，其值表示这些路径中数字之和的最大值。不难看出，对于f[i][j]中的路径，可以将其分为两类，一类是从左上方的节点下来的；另一类是从右上方的节点下来的。因此可以得到状态转移方程f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + a[i][j]。
代码实现
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, ans = 0; // 三角形的层数，ans存储答案，这里先暂时默认三角形内的数字都是正值
int a[N][N];
int f[N][N];
int main() {
cin >> n;
// 这里下标推荐从1开始，因为循环中需要用到i - 1层的值，防止下标越界
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= i; j ++) {
cin >> a[i][j];
f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + a[i][j];
}
for (int i = 1; i <= n; i ++)
ans = max(ans, f[n][i]);
cout << ans << endl;
return 0;
}一般来说线性DP的时间复杂度都不会很高，优化空间也不大。实际上背包问题也是线性DP的一类，因为背包问题得到的状态转移方程也是线性的关系。
最长上升子序列
给定一个长度为n的数字序列，求数值严格单调递增的子序列的长度最长是多少。
输入样例：3 1 2 1 8 5 6 输出样例：最长上升子序列为1，2，5，6，输出4
分析思路：对于状态表示，定义f[i]表示所有以第 i 个数结尾的所有上升子序列的集合，其值表示这些子序列最长的长度。可以将f[i]表示的集合按照倒数第二个数字分成i种，分别是无（即子序列中之后a[i]一个元素0）或a[1]，a[2]，…………a[i - 1]，这几类子序列中的最长的长度分别为1, f[1] + 1, f[2] + 1, f[3] + 1…………f[i - 1] + 1。而且必须要满足a[i] > a[j]。因此可以设计出一个两重循环分别遍历求出状态数组，最后返回f[n]。
代码实现
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, ans = 0;
int a[N];
int f[N];
int main() {
cin >> n;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
f[i] = 1;
for (int j = 1; j < i; j ++)
if (a[i] > a[j]) f[i] = max(f[i], f[j] + 1);
}
// f[n]只是以第n个元素结尾的最长子序列长度，需要遍历一遍f数组求最大值
for (int i = 1; i <= n; i ++)
ans = max(ans, f[i]);
cout << ans <<endl;
return 0;
}优化思路：如果我们要获得尽可能长的子序列，我们希望让子序列的值上升得尽可能慢，也就是说我们倾向于选择上升幅度更小的数添加到子序列中，基于这个贪心思想我们可以构造一个d数组，d[i]的值表示长度为i的最长子序列的最后一个元素的最小值，显然d数组是一个严格单调递增的数组。因为假设存在d[j] > d[i]且j < i，那么也就是说存在一个长度更长的子序列，但是其最后一个值比长度更短的子序列要小，那么这个长度为 j 的子序列的第i个数肯定比d[i]要小，与定义相矛盾。初始化d[1] = a[1]，同时维护一个len变量，记录当前找到的最长的子序列的长度，遍历a数组，对于a[i]，比较其和d[len]的大小，如果比d[len]大，则将d[len + 1]置为a[i]，同时len ++；否则找到一个 j，使得d[j - 1] < a[i] < d[j]，将d[j]设置为a[i]，因为长度为 j 的子序列的最后一个元素可以替换成a[i]了。由于d数组是严格递增的，所以查找 j 的方法可以使用二分查找。
代码实现
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, x, len;
int d[N];
// d数组下标是从1开始的，到len结束，所以l初始值为0，r初始值为len + 1
int bi_search(int x) {
int l = 0, r = len + 1;
while (l + 1 != r) {
int mid = l + r >> 1;
if (d[mid] < x) l = mid;
else r = mid;
}
return r;
}
int main() {
// 先读入一个数，用于初始化d[1]
cin >> n >> x;
d[++ len] = x;
for (int i = 1; i < n; i ++) {
cin >> x;
int idx = bi_search(x);
// 由于我们一直使用的是 ++ len，所以这里应该比较idx和len + 1
if (idx == len + 1) d[++ len] = x;
else d[idx] = x;
}
cout << len << endl;
return 0;
}时间复杂度分析：二分查找的时间复杂度为O(log n)，所以整个算法（贪心 + 二分查找）的时间复杂度为O(n log n)。对于初版的动态规划算法的时间复杂度要好上很多。
最长公共子序列
给定两个长度分别为n和m的字符串a和b，求既是a的子序列又是b的子序列的字符串长度最长是多少
分析思路：对于状态表示，因为涉及到两个字符串因此需要二维数组来分别表示两个字符串的信息。定义f[i][j]表示截至到a[i]和b[j]，两个子字符串的所有公共子序列，其值表示这些公共子序列的最大长度。对于状态计算，可以将f[i][j]表示的所有子序列分成如下四部分：既不包含a[i]也不包含b[j]，包含a[i]但不包含b[j]，不包含a[i]但包含b[j]，a[i]b[j]全部包含。这四类子序列的最大长度分别为f[i - 1][j - 1]，f[i][j - 1]，f[i - 1][j]，f[i - 1][j - 1] + 1（要求a[i]b[j]相同，然后可以将这两个字符去掉，就转化成了第一类子序列）。而第一类子序列中其实已经包含在第四类子序列中，这里因为我们是求最大值，即使重复也没关系，只要保证不漏情况就可以，所以只需要判断后面三类集合的属性的大小即可。最后返回f[n][m]即可。
代码实现
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
char a[N], b[N];
int f[N][N];
int main() {
cin >> n >> m;
cin >> a + 1 >> b + 1; // 这里为了防止第一次遍历的时候下标溢出，字符串从1下标开始读入
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++) {
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
if (a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
}
cout << f[n][m] << endl;
return 0;
}编辑距离
给出两个单词word1和word2，返回将word1转换成word2所需的最少操作次数。
对单词可以进行如下三种操作：插入一个字符、删除一个字符、替换一个字符
分析思路：
代码实现
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1000;
char a[N], b[N];
int main() {
cin >> a + 1 >> b + 1;
}先挖个坑，未完待续……
区间DP
顾名思义，区间DP就是dp数组的下标表示的是一个区间。
石子合并
有n堆石子，每堆石子地质量各不相同。现在要将石子有序地合并成一堆，每次只能选择相邻地两堆石子合并成新的一堆，每次合并石子的代价是左右两堆石子的质量之和，试求出在所有的合并石子的方式中，总代价的最小值。
分析思路：因为我们最终求的是将第一堆到最后一堆合并的最大代价，而中间又需要合并其他的小堆石子。考虑使用f[i][j]表示合并第 i 堆到第 j 堆石子的所有方式中，总代价的最小值。那么对于f[i][j]表示的集合，可以按照最后一次合并的位置将其分为如下数类：最后一次合并的位置在第一堆的后面、在第二堆的后面………最后一次合并的位置在第 i - j 堆的后面。截至到倒数第二步，这几类合并方式的最小代价分别是f[i][i] + f[i + 1][j]、f[i][i + 1] + f[i + 2][j]……f[i][j - 1] + f[j][j]，不论是哪种方式，最后一次合并的代价都是相同的个，即这个区间内所有石子的质量之和，这个区间和可以使用前缀和来解决，对于前面的 i - j 中合并代价，取最小值即可，最后输出f[1][n]即可。
需要注意的是：由于我们是利用短区间的结果来计算长区间的结果，因此在计算长区间时必须保证短区间的结果已经被计算出来了，所以枚举的条件应该按照区间长度从小到达枚举。
代码实现
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1010;
int n;
int a[N];
int f[N][N];
int main() {
cin >> n;
for (int i = 1; i <= n; i ++) cin >> a[i];
memset(f, 0x3f, sizeof f);
// 求前缀和
for (int i = 1; i <= n; i ++) {
a[i] += a[i - 1];
f[i][i] = 0;
}
// 显然f[i][i] = 0，因此从len = 2开始枚举
for (int len = 2; len <= n; len ++)
for (int i = 1; i + len - 1 <= n; i ++)
for (int k = 0; k < len - 1; k ++) {
int j = i + len - 1;
f[i][j] = min(f[i][j], f[i][i + k] + f[i + k + 1][j] + a[j] - a[i - 1]);
}
cout << f[1][n] << endl;
return 0;
}记忆化搜索
记忆化搜索本质上就是自顶向下的DP，我们前面所写的DP都是自底向上的，即先求出最小问题的答案，再利用小问题求出大问题额度结果，表现形式就是循环，通过循环自底向上递推。而记忆化搜索是自顶向下的，而且会缓存结果，即算出一个子问题之后将结果存下来，下次遇到相同问题的时候直接查表，避免重复计算，而自定向下求解问题的一个经典方式就是递归。我们前面所推导出的状态转移方程也可以写成递归形式。记忆化搜索可以直接写出状态转移的代码，而不用思考遍历顺序，下面介绍一个记忆化搜索的典型例题
滑雪
给定一个n行m列的矩阵，表示一个矩形网格滑雪场。矩阵中第i行第j列的点表示滑雪场对应区域的高度。
一个人从滑雪场的某个区域内（即矩阵的某个点）出发，每次可以向上下左右其中一个方向移动一个单位距离。移动的前提是目标区域的高度低于当前所处区域的高度。
下面给出一个例子：
1 4
2 3
在示例矩阵中，一条可行的滑雪路径是4 -> 3 -> 2 -> 1，也是最长的滑雪轨迹。
现给定一个二维矩阵表示滑雪场各个区域的高度，求出在该滑雪场中能够完成的最长滑雪轨迹，并输出其长度
分析思路：定义f[i][j]表示以第i行第j列为起点，所有可行的滑雪路径，其值表示这些路径中的最大长度。将f[i][j]表示的集合按照第一步的方向分为四类：分别是向上、向下、向左、向右。这四类路径对应的最大长度分别是f[i][j - 1]、f[i][j + 1]、f[i - 1][j]、f[i + 1][j]。当然，考虑这些方向的前提是下一步的高度要比起始高度低，否则不予考虑。这里要考虑循环依赖的问题，事实上这个问题中不会存在循环依赖的问题，假设1号区域的值依赖于2号区域，2号区域的值依赖3号区域，3号区域的值依赖于1号区域，那么根据规则，2号区域是低于1号的，而3号区域必须低于2号，1号区域又必须低于3号，矛盾。所以该问题不会存在循环依赖问题。
代码实现
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 310;
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};
int n, m, ans = 0;
int h[N][N];
int f[N][N];
int skip(int i, int j) {
// 使用引用，给f[[i][j]换一个简单的名字
int &v = f[i][j];
// 如果已经探索过这个点了，则直接返回
if (v != -1) return v;
// 路径最少为1
v = 1;
for (int k = 0; k < 4; k ++) {
int x = i + dx[k], y = j + dy[k];
if (x < 0 || x >= n || y < 0 || y >= m) continue;
// 要取所有方向的最大值
if (h[x][y] < h[i][j]) v = max(f[i][j], skip(x, y) + 1);
}
return v;
}
int main() {
cin >> n >> m;
// 初始化，表示所有点都没有搜过
memset(f, -1, sizeof f);
for (int i = 0; i < n; i ++)
for (int j = 0; j < m; j ++)
cin >> h[i][j];
for (int i = 0; i < n; i ++)
for (int j = 0; j < m; j ++)
ans = max(ans, skip(i, j));
cout << ans << endl;
return 0;
}其实本题我们也可以利用和之前相似的递推来做，但是会很麻烦，递归形式的记忆化搜索有一个好处就是代码复杂度比较低，推导出状态转移方程后就可以直接写代码了，处理的边界问题也比递推要少一些。
即使我们前面介绍了很多不同的DP模型，但是可以看到即使是同一模型的DP，思路差异也非常大，而且不同模型之间的差别也没有想象中那么大，例如背包DP就是线性DP的一种，区间DP也只是将状态数组的表示形式改变了一下而已，本质还是通过分解问题来解决大问题。本章中还有很多模型没有介绍，例如树形DP，状态压缩DP等，这几种模型也是改变了状态数组的表示形式，而且在笔试面试中考察的也不多，所以不在此过多介绍。
总的来说，DP问题没有一个通用的模板，只是有一个通用的思考方式：先思考如何表示状态，再解决状态数组的值代表什么（通常是最终答案），最核心的是要解决状态计算，推导出如何从一个状态转移到另一个状态，即求出状态转移方程，不同题目思路差异很大，还是需要通过做题积累经验，很多题目的状态表示都是靠经验猜出来的，动态规划相比前面几章更注重思路，因此更加需要题目训练。
贪心
第六章：贪心算法。如果说动态规划只是没有模板，那么贪心就是毫无章法。贪心和动态规划一样都不是某种特定算法，而是一种思想。动态规划起码还是会遵循某些基本流程的，例如状态表示，状态计算等，而贪心就是一点流程都没有。贪心的基本思想是每次都选取局部最优解，最终得到全局最优解，然而这个思想太笼统了，这个思想应用到具体题目上则更加大相径庭了。想要解决贪心的题目基本只能靠经验或者灵感，贪心问题是没有模板方法来解决的，这里介绍一些典型例题。
区间选点
给定n个闭区间[ai, bi]，要求在数轴上选取尽量少的点，使得每个区间内至少包含一个选中的点，输出选择的点的最少数量。位于区间端点的点也算在区间内。
分析思路：可以从左到右讨论区间，对于一个靠左的区间，如果想要选择一个数使得尽可能多地覆盖更多区间，那么我们会倾向于选择更大的数字，因为其他未处理的区间都在数轴右侧，我们可以选择这个区间的右端点，这样便可以尽可能覆盖更多的右侧区间。这便是一种贪心的思路，我们每次选择更可能覆盖右侧区间的点，最终的结果就就是能使用尽量少的点覆盖全部区间。
证明：首先将所有区间按照右端点从小到大排序，每次选择当前区间的右端点作为选中的点加入答案集合中，再判断下一个区间的左端点是否比上一个区间的右端点小，如果小说明上一次选中的点已经覆盖了这个区间，可以直接跳过。对于任意两个相邻的区间（第i个区间和第j个区间），同时假设i.r > j.l，即选择i的右端点可以覆盖j区间的左端点。如果我们的方案不是选择右端点，那么选择的点就可能小于j.l，那么我们就需要新选择一个点来覆盖j区间了，这样就会比贪心的方案多选择一个点，所以贪心的方案是选择点最少的方案。
代码实现
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 101000;
struct Range{
int l, r;
bool operator < (const Range& w) const {
return r < w.r;
}
} range[N];
int n, res = 1;
int main() {
cin >> n;
for (int i = 0; i < n; i ++) {
int l, r;
cin >> l >> r;
range[i] = {l, r};
}
// 按照右端点进行排序
sort(range, range + n);
int ed = range[0].r;
for (int i = 1; i < n; i ++)
// 下一个区间的左端点比上一个区间的右端点更大，说明需要选择一个新的点了
if (range[i].l > ed) {
ed = range[i].r;
res ++;
}
cout << res << endl;
return 0;
}最大不相交区间的数量
给定n个闭区间[ai, bi]，在数轴上选择若干区间使得选中的区间互不相交，输出可选区间的最大数量。
分析思路：对于贪心问题，我们的主要论证点是：贪心的解不会比全局最优解差，即可证明贪心解是全局最优解。我们依然按照区间右端点为区间从小到大排序，然后按照右端点从小到大选择区间，这样我们就可以选取尽可能早结束的区间，那么就可以选择更多区间了。证明：假设G和O分别是贪心算法选出的集合和全局最优解的集合。我们将G和O中的区间按照右端点大小从小到大排序。对于G和O中的第一个集合g1和o1，一定有g1.r <= o1.r，否则我们便可以将o1替换成g1并且保持不相交，其余区间也是类似。如此依赖我们便证明了贪心的解不会比全局最优解更差，所以贪心解便是全局最优解。
代码实现和区间选点是完全一样的，都是选择右端点
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 101000;
struct Range {
int l, r;
bool operator < (const Range& w) const {
return r < w.r;
}
} range[N];
int n, res = 1;
int main() {
cin >> n;
for (int i = 0; i < n; i ++) {
int l, r;
cin >> l >> r;
range[i] = {l, r};
}
sort(range, range + n);
int ed = range[0].r;
for (int i = 1; i < n; i ++)
// 不相交才选择下一个区间
if (range[i].l > ed) {
ed = range[i].r;
res ++;
}
cout << res << endl;
return 0;
}区间分组
给定n个闭区间[ai, bi]，将这些区间分成若干组，使得每组内部的区间两两之间没有交集，并使得组数尽可能小，输出最小组数
分析思路： 依然将区间按照左端点进行排序，依次遍历每个区间，查找当前区间是否可加入已经存在的组（判断当前区间的左端点是否大于当前分组的最大右端点），如果可以加入则更新对应组的最大右端点，否则新建一个组。证明思路和前面类似，这里不再给出。如何快速地判断当前区间是否可以加入某个分组呢？可以维护一个小根堆，如果当前区间的左端点已经小于最大右端点最小的那个分组了，那么肯定所有分组都放不下这个区间了，就需要新开一个分组了，如果能放下，那么直接将这个区间加入最大右端点最小的那个分组即可。
代码实现
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int N = 100010;
struct Range {
int l, r;
bool operator < (const Range& w) const {
return l < w.l;
}
} range[N];
int n, ans = -1;
int main() {
cin >> n;
for (int i = 0; i < n; i ++) {
int l, r;
cin >> l >> r;
range[i] = {l, r};
}
sort(range, range + n);
// 初始化小根堆
priority_queue<int, vector<int>, greater<int>> q;
for (int i = 0; i < n; i ++)
if (q.empty() || q.top() >= range[i].l) q.push(range[i].r);
else {
q.pop();
q.push(range[i].r);
}
cout << q.size() << endl;
return 0;
}区间覆盖
给定n个闭区间[ai, bi]以及与一个线段区间[s, t]，选择尽量少的区间，将线段区间完全覆盖，输出最少区间数，如果不能完全覆盖则输出-1.
分析思路：先将所有区间按照左端点升序排序，然后依次遍历。对于要选择的区间，我们当然希望这个区间的右端点越靠右越好，因为这样就可以覆盖目标区间的更多部分。因此我们的思路就是按照左端点从小到大遍历所有区间，找到右端点最大并且左端点在待覆盖区间左侧的区间，加入答案区间中，然后将新的待覆盖区间的左端点设为我们刚才找到的区间的右端点，然后重复以上步骤。
对于这个方法的正确性的证明：假设我们自己的答案区间是cnt，最优解答案是ans。假设ans和cnt的前i个区间是相同的（ i 可以为0），对于第 i+ 1 个区间，由于我们每次选择的都是右端点最大的区间，因此在ans中该区间的右端点一定是小于等于cnt中的区间右端点的，此时我们便可以将ans中的第 i+ 1 个区间替换为cnt中更长的区间，并且保持总区间数不变，之后的区间也可以这样处理。这样一来我们便证明贪心解不会比全局最优解差，从而贪心解就是全局最优解。
代码实现
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
struct Range {
int l, r;
bool operator < (const Range& w) const {
return l < w.l;
}
} range[N];
int n;
int st, ed;
int main() {
cin >> st >> ed; // 输入目标区间
cin >> n;
for (int i = 0; i < n; i ++) {
int l, r;
cin >> l >> r;
range[i] = {l, r};
}
sort(range, range + n);
int res = 0, right = -2e9;
for (int i = 0; i < n; i ++) {
int j = i;
while (j < n && range[j].l < st) {
right = max(right, range[j].r);
j ++;
}
if ()
}
}Huffman树（再探石子合并）
有n堆石子，每堆石子地质量各不相同。现在要将石子有序地合并成一堆，每次可以选择任意两堆石子合并成新的一堆，每次合并石子的代价是两堆石子的质量之和，试求出在所有的合并石子的方式中，总代价的最小值。
分析思路：再看这道石子合并问题，与之前的石子合并问题不同的是，之前只能合并相邻两堆石子，本问题中可以合并任意两堆石子。这其实是一道典型的Huffman树问题，Huffman树可以用贪心算法解决，我们用一棵树表示石子的合并过程，所有叶节点表示初始的石子质量，每次合并都将对应的叶节点连接到同一个父节点上，父节点的值为子节点的值之和，直到整个树只剩一个根节点，这个节点的值就是整个合并过程的代价。构造Huffman树的过程很简单，每次都将质量最小的两个节点作为叶子节点合并即可。
想要快速取出最小的两个节点也很简单，直接维护一个堆即可。
证明：通过举一些简单的例子不难发现，最终的总代价 = Σhimi，其中hi表示i号节点的深度。如果质量最小的节点不是每次合并的叶子节点，那么可以将叶子节点和其他节点交换，假设交换himi和hjmj，显然质量越小的节点越先被合并，其深度h也就越大，假设mi < mj，那么显然有hi > hj，因为i号节点先于j号节点和合并，如果交换这两个节点在树中的位置，不难看出himj > hjmi，所以此时总代价就会增大，故我们构造的Huffman树是总代价最小的树。
代码实现
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100010;
int n, res;
priority_queue<int, vector<int>, greater<int>> q;
int main() {
cin >> n;
for (int i = 0; i < n; i ++) {
int a;
cin >> a;
q.push(a);
}
// 不断合并直到只剩一堆石子
while (q.size() > 1) {
// 每次选择质量最小的两堆石子合并
int a = q.top();
q.pop();
int b = q.top();
q.pop();
res += a + b;
q.push(a + b);
}
cout << res << endl;
return 0;
}排队打水
有n个人排队打水，每个人打水需要的时间是ti，同时最多只能有一个人打水，其他人必须等待，问如何安排打水顺序，能使所有人的等待时间之和最短。输出最短时间
分析思路：所有人的等待时间 = Σtin，其中n为等待第i个人打水的人数，显然越先打水的人，等待他打水的人就越多，相应的n也就越大，即权重更高，所以我们更加倾向于让打水时间更短的人先打水，这样在n相同的情况下，选择更小的ti，可以让总的等待时间更短。打水时间长的人后打水，其权重就会变低，总等待时间也就越少。
代码实现
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100100;
// 这里需要关注一下数据范围，如果数据范围比较大可能会爆int，需要使用long long
int n, res;
int a[N];
int main() {
cin >> n;
for (int i = 0; i < n; i ++) cin >> a[i];
// 将数组按照从小到大排序
sort(a, a + n);
for (int i = 0; i < n; i ++) res += a[i] * (n - i - 1);
cout << res << endl;
return 0;
}小结：解决贪心问题的核心是证明贪心得到的解是全局最优解，一般的证明思路是证明贪心的解不会比全局最优解更差从而证明贪心解就是全局最优解。通过本章的例题可以看到贪心的问题一般没有一个通用的解决问题的方法论，绝大部分的贪心问题都是从猜开始的，即猜想一种贪心思路，然后证明这个贪心思路可以得到全局最优解，但很多时候我们并不许需要很严格的证明，甚至只需要一个大概的证明即可，这也导致了贪心很难想到正确的思路。贪心的问题往往是靠经验或灵感猜出思路的。想要解决贪心的问题也是需要多做题积累经验的，多多见识不同的思路和解题方法。