1. 贪心算法每一步都选当前最优但这只是表象1.1 贪心的本质局部最优如何变成全局最优贪心算法可能是这四个思想里最容易“上手”的也是最容易“翻车”的。它的核心就一句话每一步都做当前看起来最好的选择不回头、不试探、不后悔。听起来像极了生活中“先把手头最急的事做完”的时间管理策略但算法里的贪心远比这句话严谨。真正靠谱的贪心策略必须满足一个隐藏条件局部最优能够一步步推导出全局最优。换句话说你在每个子问题上做的“最优决策”合并起来之后恰好就是整个问题的最优解。这个性质叫“最优子结构”它和动态规划里的要求很像但贪心比DP更“固执”——DP会把所有可能都算一遍贪心只选一条路走到黑。举个例子你立马就懂了。区间调度问题给你一堆活动每个活动有开始时间和结束时间问最多能参加多少个不冲突的活动。标准解法是按结束时间从小到大排序然后从头往后扫能选就选。这里“能选就选”就是贪心。为什么按结束时间排序而不是按开始时间或者活动时长因为结束得越早后面留下的空档就越大你才有更多机会安排后续活动。这个直觉经过“交换论证”可以严格证明任何一个最优解中如果第一个活动不是当前结束时间最早的那把它换成结束时间最早的后面的活动依然能全部安排下结果不会变差于是贪心解就是最优解。1.2 贪心的适用场景到底哪些题能用贪心判断一道题能不能用贪心我的经验是先问你三个问题。第一这个问题的决策是否存在先后依赖并且每一步做完之后不会影响之前的决策第二是否存在一个简单的“排序键”或“比较规则”能描述“看起来更好”的标准第三能不能反例构造失败构造不出来再往贪心方向想。最常见的贪心模型包括区间调度与区间覆盖、哈夫曼编码、最小生成树的Kruskal和Prim、Dijkstra最短路、找零钱问题里的“尽量用大面额”策略、以及各种“最大化最小值”问题里配合二分答案的check函数。注意找零钱只有在货币面额满足一定条件比如人民币的1、2、5、10这种倍数关系时贪心才正确换成面额为1、5、11的货币体系贪心就会出错。这不是说贪心不行而是贪心的前提条件不满足。很多同学一上来就想用贪心是因为贪心写起来最快。但实际刷题时我更建议拿到题目先花两分钟构造一个能驳倒“局部最优等于全局最优”的极端例子。构造不出来再动手写。1.3 一个经典贪心例题的完整实现拿区间调度这个最经典的模型来写一遍完整代码。题目输入n个活动每个活动有开始时间s和结束时间e选出尽量多的互不重叠的活动。#include bits/stdc.h using namespace std; struct Activity { int s, e; }; int main() { int n; cin n; vectorActivity acts(n); for (int i 0; i n; i) { cin acts[i].s acts[i].e; } // 关键按结束时间升序排序 sort(acts.begin(), acts.end(), [](const Activity a, const Activity b) { return a.e b.e; }); int ans 0, lastEnd -1; for (const auto act : acts) { if (act.s lastEnd) { ans; lastEnd act.e; } } cout ans endl; return 0; }这段代码里最值得注意的就是排序规则。如果按开始时间排序可能选到一个特别长的活动把后面全挡死如果按时长排序可能选到两个不相邻却挡路的活动。只有按结束时间排才能保证每次选的“代价”最小、收益最大。这个“收益/代价”的思维就是贪心策略设计的核心。我见过不少人会把lastEnd初始化为第一个活动的结束时间然后从第二个开始遍历。这样写也正确但泛化到“区间选点”“区间覆盖”等变体时容易出错。统一写成lastEnd -1从第一个活动开始判断逻辑更干净边界也更少。1.4 贪心最经典的坑0/1背包就贪不了提到贪心就不得不泼一盆冷水0/1背包问题不能用贪心求解。很多初学同学会想“那我按单位重量价值从高到低装不就行了”听起来很有道理但反例太好构造了背包容量10物品A重量6价值9单位价值1.5物品B重量5价值7单位价值1.4物品C重量5价值7单位价值1.4。按单位价值贪心先装A剩下的4装不下任何东西总价值9而最优解是装B和C总价值14。问题出在背包容量是离散的、物品不可分割贪心只考虑了“当前最划算”却忽略了“装完之后剩下的空间是否还有用”。这就是贪心和动态规划的分界线。决策会影响后续可用资源时贪心通常不是安全选择。所以在正文里我经常强调贪心适合“决策之间相互独立”的场景DP适合“决策之间相互依赖、需要全局权衡”的场景。判断错误是最致命的比代码写错更浪费时间。2. 二分把“求答案”变成“验证答案”2.1 二分查找和二分答案是两个级别的东西如果你还停留在“二分就是在一个有序数组里找某个数”那今天之后可以把它升级为一个更强的思想二分答案。两者底层逻辑一样都依赖单调性但应用范围完全不同。二分查找是在已知的序列上做搜索序列本身有序你要找目标值。二分答案则是对“答案的值域”做二分每次取一个中间值然后写一个check(mid)函数验证这个值是否可行根据验证结果把搜索区间缩小一半。二分答案的本质是把一个“求最优解”的问题转化成“给定一个解判断它是否可行”的判定问题。两者最大的区别在于切入点。二分查找关心“目标在哪里”二分答案关心“目标是多少”。后者明显更抽象、更强大因为很多最优解问题你根本不知道答案是多少但你可以快速验证一个值行不行。2.2 整数二分的边界问题一个值等于守住不掉进死循环我见过太多人在整数二分里栽跟头核心问题就出在mid的取法和区间缩小的写法上。第一种写法求“第一个满足条件的位置”int l 0, r n - 1; while (l r) { int mid (l r) 1; // 向下取整 if (check(mid)) r mid; // mid 满足就向左收 else l mid 1; // mid 不满足就排除掉 }第二种写法求“最后一个满足条件的位置”int l 0, r n - 1; while (l r) { int mid (l r 1) 1; // 向上取整 if (check(mid)) l mid; else r mid - 1; }注意第二个模板里的mid (l r 1) 1这一步是防止死循环的关键。当l和r相邻时如果mid (l r) 1那么mid等于l一旦check(mid)为真l mid就是原地踏步死循环。所以“取中点上取整”和“左边界更新为mid”必须配套出现。同理第一个模板里r mid不会原地踏步因为mid向下取整保证了mid严格小于r。提示背模板不重要理解“为什么向下取整配合左小右大”“为什么向上取整配合左大右小”才是关键。每次写二分先在草稿纸上画一条数轴模拟l和r相邻时的情况就能避免绝大多数死循环。2.3 完整例题最大化最小值牛棚问题直接上二分答案最常见的例题。题目大意有n个牛棚位置在数轴上要安排m头牛进去使得任意两头牛之间的最小距离尽可能大。这个问题正着求最优解非常难因为你不知道最优距离是多少。但反过来如果我给定一个距离d判断“能否放下m头牛”就容易多了从第一个牛棚开始放牛往后找到第一个距离上一次放牛位置不少于d的牛棚就再放一头能放满m头说明d可行。这个check里的贪心就是典型的“能放就放”。距离越大越难放满所以可行性关于d是单调递减的完全具备二分条件。#include bits/stdc.h using namespace std; int n, m; vectorint x; bool check(int d) { int cnt 1, last x[0]; for (int i 1; i n; i) { if (x[i] - last d) { cnt; last x[i]; if (cnt m) return true; } } return false; } int main() { cin n m; x.resize(n); for (int i 0; i n; i) cin x[i]; sort(x.begin(), x.end()); int l 0, r x[n - 1] - x[0], ans 0; while (l r) { int mid (l r) 1; if (check(mid)) { ans mid; l mid 1; } else { r mid - 1; } } cout ans endl; return 0; }这段代码里check的目标是验证“距离至少为d时能不能放m头牛”。为什么排序因为只有先排序才能保证牛棚位置可以按顺序遍历也才能用“相邻距离是否大于等于d”来判断可行性。不排序的话这个贪心策略根本不成立。2.4 二分的坑单调性和浮点数二分写二分答案最容易忽略的一点是“单调性必须和check的方向一致”。check(mid)为真说明 mid 可行但可行区间是左边还是右边完全看你的题面。最大化最小值问题里d越大越难放满所以 mid 可行就要往大的方向找最小化最大值问题里容量越小越难满足所以 mid 可行就要往小的方向找。这两者恰好相反写反了就直接全错。浮点数二分是另一个常考场景。写法上通常把while (l r)换成for (int i 0; i 100; i)或者while (r - l 1e-6)因为浮点数没有“相邻整数”的概念用误差范围控制循环更稳定。关键看的不是循环次数写多少而是你要保证二分区间长度在每次循环中稳定减半100次二分能把1e9的区间缩小到约1e-21足够绝大多数题目的精度要求。用r - l eps反而容易因为精度设置不当进入死循环或者精度不够我个人的习惯是直接循环80到100次省心。3. 正难则反所有难题都值得反向思考一次3.1 什么时候应该第一时间想到“反过来做”“正难则反”不是某个具体算法而是一种解题策略。很多题目正着做要维护复杂的状态、处理麻烦的动态过程但如果从终态往回推或者从整体中减去反面情况计算量能瞬间降一个数量级。最常见的识别信号有三个题目里出现“删除”二字正着做要维护删除后的连通性、最值或集合信息非常麻烦而倒着当成“逐步添加”来做反而简单题目里问“至少有一个”“存在一个”“全部中满足条件”等概率或计数问题先用总数减去“一个都没有”的反而快题目里要你“从起点到终点的最优化路径”有时候从终点反向做动态规划或者反向跑图状态转移会更直接。我在刷题时发现一个规律读题之后如果正着想出来的做法复杂度是O(n^2)或者O(n log n)再套个复杂数据结构而且代码怎么都写不顺那大概率不是你的编码能力有问题而是方向错了。这时候停下手里的set、线段树问一句“反过来能不能做”经常能柳暗花明。3.2 三种最常出现的反向套路第一种是补集法。例如“给一个数组求所有子集中和为k的方案数”直接枚举子集是O(2^n)但改成用01背包求“子集中和为k的方案数”再减去限定条件复杂度就可控了。注意补集法的前提是“全集很容易求”这样用“全集减补集”的思路才有意义。第二种是倒序处理。最典型的就是并查集配合“删除操作”。并查集天生擅长“合并”不擅长“删除”。题目让我们反复删边、删点并查询连通性正着做要维护动态删除后的并查集非常复杂把整个操作序列读进来从最后一次删除开始倒着执行变成逐步加边加点每次操作就变成了一次普通的 union。操作完成后的答案记录下来最后反转输出即可。第三种是反向遍历和反向建图。拓扑排序有时候正向跑不出来反向建图跑反而满足依赖关系最短路径如果多起点单终点可以反向建图后只跑一次最短路动态规划里状态定义“从i到终点”往往比“从起点到i”更好推比如跳台阶问题的变体、数字三角形从下往上推。3.3 完整例题倒序并查集解决删点问题题面可以简化成一个n个点m条边的无向图依次删除q个点问每次删除后图中有多少个连通块。正着做需要支持并查集删除点做不到。倒着做先读入所有删除操作只保留最终没被删掉的点和它们之间的所有边统计连通块数然后逆序把删除的点一个个加回来每次加点会带来若干新边用并查集合并更新连通块数。核心代码如下#include bits/stdc.h using namespace std; const int MAXN 1005; vectorint g[MAXN]; int fa[MAXN], del[MAXN], ans[MAXN]; bool erased[MAXN]; int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } void merge(int a, int b) { int ra find(a), rb find(b); if (ra ! rb) { fa[ra] rb; } } int main() { int n, m; cin n m; for (int i 0; i n; i) fa[i] i; vectorpairint, int edges(m); for (int i 0; i m; i) { cin edges[i].first edges[i].second; g[edges[i].first].push_back(edges[i].second); g[edges[i].second].push_back(edges[i].first); } int q; cin q; vectorint op(q); for (int i 0; i q; i) { cin op[i]; erased[op[i]] true; } // 初始并查集只合并最终没被删掉的点 int components n - q; // 只有没被删的点计入初始连通块基数 for (int i 0; i m; i) { int u edges[i].first, v edges[i].second; if (!erased[u] !erased[v]) { if (find(u) ! find(v)) { merge(u, v); --components; } } } // 倒着加回被删的点 for (int i q - 1; i 0; --i) { int u op[i]; erased[u] false; components; // 添加一个孤立点连通块 1 for (int v : g[u]) { if (!erased[v]) { if (find(u) ! find(v)) { merge(u, v); --components; } } } ans[i] components; } for (int i 0; i q; i) { cout ans[i] \n; } return 0; }这个问题的核心难点就是意识到“倒着做”。一旦方向转过来实现难度直接从“不会”降到“模拟题”。这也是我强烈建议刷题时多积累反向套路的原因很多题正着做是省选题反着做就是普及题。3.4 正难则反的识别信号速查我整理了一些高频出现“正难则反”的题眼帮助你快速定位出现“删除、移除、损坏、停电”等词汇时优先考虑倒序加回出现“至少有一个满足”这种概率/计数问题优先考虑总数减“全不满足”出现“从终点倒推”的路径最优化优先考虑反向DP或反向图出现“拆分、分割”问题有时候反向思考“合并”更容易出现“最小化最大值中的最大值”这类嵌套考虑用二分答案把最内层反过来验证。说到底正难则反的本质是把“维护困难状态”变成“构造简单状态”。你不需要每一步都从反面想但当你发现正面的数据结构越堆越复杂、代码越写越臭的时候这就是大脑在提醒你是时候反过来试试了。4. 完全背包与多重背包0/1背包的两个重要变体4.1 从0/1背包的递推公式说起0/1背包应该是动态规划入门的第一课有n个物品每个物品体积v、价值w背包容量V每个物品最多选一次问能装下的最大价值。标准代码是外层物品、内层容量倒序for (int i 1; i n; i) { for (int j V; j v[i]; --j) { dp[j] max(dp[j], dp[j - v[i]] w[i]); } }dp[j]表示容量为j的背包能装下的最大价值。内层为什么要倒序因为要保证每个物品只被选一次。正序遍历的话dp[j - v[i]]可能已经在当前物品的循环里被更新过相当于同一个物品被反复放入正好成了完全背包的逻辑。倒序遍历则确保dp[j - v[i]]引用的是“还没考虑当前物品”的旧状态从而保证只选一次。这个细节一定要理解透因为完全背包和0/1背包的代码差异只在这一行内层循环方向相反。4.2 完全背包正序枚举背后的“无限次取用”完全背包是指每个物品可以取无限次。类比成“超市里同一种商品可以拿多件但要满足总重量不超过购物车容量求最大总价值”。核心代码for (int i 1; i n; i) { for (int j v[i]; j V; j) { dp[j] max(dp[j], dp[j - v[i]] w[i]); } }内层从v[i]到V正序遍历因为dp[j - v[i]]可能是本轮循环刚更新过的值意味着当前物品已经被选了一次再选一次也合法效果就是“可以取无限次”。这正是0/1背包和完全背包唯一的区别。不过要注意完全背包这里的状态转移并没有显式地写“选了几件”。它不是一件一件地枚举数量而是通过正序遍历让每一件物品可以在后续容量的更新中反复参与决策。理解这一层你才能真正明白为什么O(nV)就能解决无限选择的问题。4.3 多重背包二进制拆分的原理与实现多重背包介于两者之间每个物品有数量限制s既不是只能选一个也不是无限选。最简单的做法是再加一层循环枚举用几个复杂度O(n * V * s)当s很大时直接超时。二进制拆分是最高效的优化之一把s件物品按“1、2、4、8、...、剩余”的方式打包成若干组新物品每组是一个大物品体积是原来单件的k倍价值也是原来单件的k倍。为什么按二进制拆因为任何整数s都能用若干个2的幂次加上余数唯一凑出来比如13 1 2 4 6。这样最多拆出约log2(s)组问题就变成了0/1背包总复杂度降到O(n * V * log(s))。构造代码struct Item { int v, w; }; vectorItem goods; // 对第i个物品体积v价值w数量s for (int k 1; k s; k 1) { goods.push_back({v * k, w * k}); s - k; } if (s 0) { goods.push_back({v * s, w * s}); }之后对所有goods跑一遍0/1背包的倒序循环即可。要注意s - k必须在每次拆完一组后更新否则会多拆导致组合出来的总数超过原始数量。进一步优化可以用单调队列把复杂度压到O(n * V)。思路是枚举余数r每组背包容量按体积v分成一条链在链上做滑动窗口取最大值。这个实现细节偏多笔试手写起来容易出错我个人建议先把二进制拆分写熟练遇到直接卡复杂度的大数据再上单调队列不要一开始就追求最优解。4.4 一个完整例题多重背包的二进制拆分实现题面一个旅行者有一个容量V的背包有n种物品每种物品体积v、价值w、数量s问最大能带走多少价值。#include bits/stdc.h using namespace std; struct Item { int v, w; }; int main() { int n, V; cin n V; vectorItem goods; for (int i 0; i n; i) { int v, w, s; cin v w s; for (int k 1; k s; k 1) { goods.push_back({v * k, w * k}); s - k; } if (s 0) { goods.push_back({v * s, w * s}); } } vectorint dp(V 1, 0); for (auto item : goods) { for (int j V; j item.v; --j) { dp[j] max(dp[j], dp[j - item.v] item.w); } } cout dp[V] endl; return 0; }这里我用了结构体存物品而不是直接在原数组上操作因为拆出来的新物品组数不确定用vector存放更灵活。实际工程里也建议把“拆包”和“背包DP”两阶段分开逻辑清晰也便于调试。4.5 背包家族的其他常见变形你在刷题时还会见到恰好装满背包时求最值初始化时把dp[0]0、其他dp[j]-INF求方案数把max换成sum初始dp[0]1二维费用背包多一维容量就多一层循环分组背包每组最多选一个外层枚举组、内层倒序容量、再枚举组内物品。这些变形都建立在0/1背包的框架上理解了根本的状态转移逻辑剩下的都是加维度、改初始化的小事。顺带说一句背包问题里“贪心不可用”的原因在第1章已经用反例展示过这正好说明DP的“枚举所有状态”是有代价的而这个代价有时是必要且值得的。5. 组合拳这四个思想在真题里从来不单独出现5.1 二分答案 贪心check 的最强组合你在比赛中会频繁遇到“最大值最小化”或“最小值最大化”类型的题解法几乎固定为二分答案加贪心check。前文的牛棚问题就是典型但同类的还有“把一堆货物分成m段每段和的最大值尽量小”“在一条直线上选k个点使相邻点最小距离最大”等。为什么check里常用贪心因为贪心的代码简单、常数小只需要验证可行性而不需要确切的方案所以“能用就用”。比如分段问题check里的贪心就是“能塞进当前段就塞塞不下再开新段”段数不超过m就可行。这种“在验证过程中用贪心构造方案”的思路把两个思想完美结合了起来。我平时做题会先看题面是不是“最优值问题”、答案是不是一个整数或浮点数值域、是否存在“给答案后容易验证”的check函数。这三条都满足大概率就是二分答案了。5.2 正难则反 背包补集法求方案数有一种常见题目“从n件物品中选若干件要求总重量大于等于某个阈值的方案数”。直接枚举所有满足要求的方案很难因为“大于等于”没有固定边界。反过来做就简单了总方案数为2^n每件物品选或不选用背包求出总重量小于阈值的方案数两者相减就是答案。这里的背包就是0/1背包求方案数状态定义是“前i件物品凑出总重量j的方案数”转移时加上选和不选两条路径。这类题的关键在于你能不能识别出“总数减去不合法”这个方向。如果正面纠结于“至少”“至少超过多少”这类非精确条件八成就是没想反向。5.3 贪心 背包 / 二分 背包的嵌套结构有些综合性较强的题会在背包外面套一个二分。例如“给定背包容量每种物品有数量上限问在价值不少于目标值的前提下背包容量最小是多少”。正着求没有单调性但你可以二分背包容量check函数用多重背包判断该容量下能不能凑出目标价值。外层二分的l和r就是背包容量的上下界内层跑一个二进制拆分后的0/1背包。这类题对数据范围很敏感V不能太大否则O(V log s)的内层会被二分的外层反复调用导致复杂度爆炸。遇到这种题先看V和n的范围再决定用二进制拆分还是单调队列优化。我见过一个常见的错误写法在外层二分里写while (l r)内层背包却用完全背包模板导致每个物品无限取。这种低级错误往往发生在你连续刷了好几题、模板背串的时候。解决办法只有一个每一道背包题动手前先明确“这个物品能取几次”再对照模板把里层循环方向写对。6. 实战避坑速查表与个人经验6.1 高频问题与解决方案速查问题现象根本原因解决方案贪心代码短小却答案错误局部最优不能推出全局最优构造反例验证改用DP或搜索整数二分死循环mid取法与区间更新不配套记住“向下取整配rmid向上取整配lmid”二分答案结果偏小/偏大check方向搞反明确是“越大越可行”还是“越小越可行”倒序并查集答案顺序错误忘了把结果反转输出逆序遍历操作时先记录再反序输出完全背包写成了0/1背包内层循环方向写错看物品能否无限取用决定正序还是逆序多重背包超时三重循环复杂度太高用二进制拆分降复杂度二进制拆分数量出错拆完一组没用s - k每次拆分后更新剩余数量背包求方案数时结果错初始化dp[0]没设为1方案数DP要记得dp[0]1这张表是我自己刷题时反复踩坑后的总结。每次在线上比赛或笔试里遇到上述问题我都会先对着这几个方向排查基本能快速定位。6.2 我的练习顺序建议这四个思想如果按学习难度排列我觉得是二分最简单、贪心次之、背包需要一点DP基础、正难则反最吃经验。所以我的建议练习顺序是二分一次到位把整数二分和浮点数二分每种模板刷十道题以上贪心配合区间类问题刷同时注意收集反例背包从0/1学起再学完全背包最后啃多重背包的二进制拆分正难则反不用刻意刷遇到一道收录一道积累题感。刷题的时候别急着看题解。我习惯是卡题20分钟如果完全没有思路就先把题目里出现的高频词和“正难则反”的信号对照一遍再决定要不要看题解。很多时候你以为自己是算法不会其实只是没把学过的思路用上。6.3 最后分享一个实际项目中的小操作我记得有次做算法课的项目需要处理一个资源分配的优化问题。题目本身是个带数量上限的分配模型正着枚举方案数量爆炸。我当时就是先二分答案确定单位收益的上下界check函数里用贪心把资源按优先级塞进槽位再用多重背包的二进制拆分思想把同类型资源合并计算三个思想同时用上最后性能比同学用暴力搜索快了接近两个数量级。那一版代码我现在还留着每次提到“算法思想组合拳”我都会拿它当例子。后来我把这些思想沉淀成一套固定的解题流程先读题看出题类型再看数据范围决定复杂度然后按“二分答案可用性、贪心安全性、反向思考信号、背包建模”四个维度扫描一遍。这个流程对面试和竞赛都适用也是我写这系列文章想传达的核心习惯。练算法没有捷径但思路可以复用。这一篇把贪心、二分、正难则反、完全背包、多重背包放在一起过了一遍它们就像工具箱里的几把常用扳手单看都不复杂真正的功夫在于面对一道新题时知道该拿起哪一把、怎么组合着用。多刷题、多总结、多复盘比背再多模板都管用。