算法设计期末 · 分治贪心动规
这张图讲什么
「算法设计期末 · 分治贪心动规」是 SeekFlaw 编辑团队整理的思维导图,分 7 个一级分支:先判断:这道题该用哪种方法;分治法:分解、求解、合并;贪心法:选对策略并证明它;动态规划的写法:状态、转移与边界;动态规划的经典模型;回溯法与分支限界法;方法对照:反例、区别与复杂度,共 68 个节点、67 张记忆卡,含 6 张配图。
这张图按「先选方法,再学写法」组织:先用对照表判断题目该用分治、贪心、动态规划还是回溯;再按方法逐个讲设计要点和经典题,动态规划单独分成「写法」和「经典模型」两枝;最后用反例和对照辨析易混点。建议先看第一枝,动态规划两枝配合着填表练;答题时把状态、转移、边界、答案位置四样写清。
5 个要点
- 先判断:这道题该用哪种方法——算法设计题的第一步不是写代码,而是判断方法:子问题互相独立、合并容易,用分治;有贪心选择性质,用贪心;子问题重叠、有最优子结构,用动态规划…
- 分治法:分解、求解、合并——分治三步:分解成同类的小问题,递归求解,再合并。
- 贪心法:选对策略并证明它——贪心题的关键不是写代码,而是选对贪心策略并证明它对:按什么顺序排序、每次选什么。
- 动态规划的写法:状态、转移与边界——动态规划题的答案一般要写清四样:状态定义(dp 数组每个下标代表什么)、转移方程、边界、填表顺序与答案位置。
- 动态规划的经典模型:经典模型各记一个状态定义和一个转移:最大子段和与最长上升子序列(以 i 结尾)、最长公共子序列与编辑距离(两个前缀)、背包(前 i 件…
适用:大学期末复习。用法:点开任一节点先自己答,再翻面核对。
配图:最大子段和分治:左半、右半和跨中点三种位置;六个活动的时间轴,按结束时间选出 3 个;面值 1、3、4 凑 6:贪心 3 枚,最优 2 枚,以及 f 表;X=ABCD、Y=ACBD 的最长公共子序列填表;容量 5、三件物品的 0-1 背包 dp 表与还原过程;4 皇后两个解的棋盘。
发布于
一句话:这张图把「算法设计期末 · 分治贪心动规」整理成 68 个节点、67 张记忆卡;点开节点翻面就能看答案。
按题型选方法:分治、贪心、动态规划、回溯与分支限界,写清状态、转移和边界,配自编算例与反例,适合算法设计与分析课程期末复习。点开任一节点翻面看答案,登录后可存进自己的空间,按遗忘曲线复习。
SeekFlaw 求瑕是面向初中、高中、考研、考公考前速记的思维导图与记忆卡平台:把课件、讲义变成思维导图,节点翻面就是记忆卡,按遗忘曲线安排复习。
68 个节点 · 67 张记忆卡。作者:SeekFlaw 编辑团队;发布于 2026-11-20。
先看这 3 条
- 分治、贪心、动态规划、回溯各适合什么题:按 子问题之间的关系 区分:分治的子问题相互独立;动态规划的子问题重叠,要存表复用;贪心每步只做一个局部最优选择,不回头;回溯在解空间里系统搜索,走不通就退回。
- 动态规划的解题步骤是什么:常写成五步:①分析最优解的结构,确认有最优子结构;② 定义状态 ;③写出 转移方程 (用更小的状态表示当前状态);④确定边界;⑤确定填表顺序和答案在表里的位置。
- 贪心和动态规划有什么区别:贪心每步只做一个选择、 不回头 ,只留下一个子问题;动态规划对所有可能的选择都求出子问题的最优值,再从中择优。
先判断:这道题该用哪种方法
- 分治、贪心、动态规划、回溯各适合什么题:按 子问题之间的关系 区分:分治的子问题相互独立;动态规划的子问题重叠,要存表复用;贪心每步只做一个局部最优选择,不回头;回溯在解空间里系统搜索,走不通就退回。 记法 求最优值且子问题重叠 → 动态规划;每步有明显的最优选择且能证明 → …
- 什么是最优子结构,怎么判断:问题的最优解里包含子问题的最优解:把最优解拆开,每一部分在对应的子问题上也是最优的。动态规划和贪心都以它为前提。 例 最短路径:A 到 C 的最短路经过 B,则其中 A 到 B 这一段也是 A 到 B 的最短路,否则换成更短的一段,整条路…
- 什么是重叠子问题,为什么它让动态规划更快:递归求解时 同一个子问题被反复计算 ,叫重叠子问题;动态规划把每个子问题只算一次并存起来,总时间降为「状态个数乘每个状态的转移代价」,常能把指数级压成多项式级(背包是伪多项式)。 例 $F(0)=0$,$F(1)=1$,$F(n)=F(n…
- 贪心法要满足哪两个性质:① 贪心选择性质 :存在一个整体最优解,它的第一步就是当前的局部最优选择;② 最优子结构 :做出这一步之后,剩下的子问题的最优解与这一步合起来仍是整体最优。 易错 「每步选当前最好的」不等于贪心正确,必须证明;举不出反例只是旁证,不是证明…
- 回溯法适合什么题,和穷举有什么区别:回溯法适合求 满足约束的全部解或一个可行解 (排列、组合、子集、着色一类):在解空间树上深度优先搜索,走不通就退回上一步;穷举则是不剪枝地把所有可能都试一遍。 例 4 皇后:前两行皇后放在第 1 行第 1 列、第 2 行第 3 列时,第 …
- 常见题型和方法怎么对号入座:先看题目要什么,再对号入座: 贪心: 活动安排 、区间选点、哈夫曼编码、分数背包、最优服务次序、最小生成树 动态规划: 0-1 背包 、最长公共子序列、最长上升子序列、编辑距离、矩阵连乘、最大子段和 分治:归并排序、快速排序、二分搜索、大…
分治法:分解、求解、合并
- 分治法的三个步骤和适用条件:三步:分解(把问题分成 a 个规模为 $n/b$ 的同类子问题)、求解(递归;规模小到可以直接求)、合并(把子问题的解合成原问题的解)。时间满足 $T(n)=aT(n/b)+f(n)$,$f(n)$ 是分解与合并的总代价。 条件 子问题 …
- 最大子段和的分治解法怎么设计:把序列从中间分成两半,最大子段只可能在三个位置:全在左半、全在右半、 跨过中点 。前两种递归求,第三种 = 左半「以中点结尾」的最大后缀和 + 右半「以中点后一个元素开头」的最大前缀和,取三者最大。$T(n)=2T(n/2)+O(n)$,…
- 快速排序与归并排序的分治有什么不同:两者都是分治,差别在 工作量放在哪一步 :快速排序的难点在分解(划分),合并什么也不用做;归并排序分解很简单(对半分),难点在合并。 区分 快速排序:分解 $O(n)$,合并 $O(1)$,划分极不均匀时最坏 $O(n^2)$;归并排序:…
- Strassen 矩阵乘法为什么比普通分块乘法快:普通分块把 $n\times n$ 矩阵分成 4 块,要做 8 次 子矩阵乘法,$T(n)=8T(n/2)+\Theta(n^2)=\Theta(n^3)$;Strassen 只做 7 次 (多做一些加减法),$T(n)=7T(n/2)+…
- 大整数乘法怎样把 4 次乘法减成 3 次:设 $X=A\cdot10^{m}+B$,$Y=C\cdot10^{m}+D$(各 ${2m}$ 位)。$XY=AC\cdot10^{2m}+(AD+BC)\cdot10^{m}+BD$,直接算要 4 次 m 位乘法,$T(n)=4T(n…
- 棋盘覆盖问题的分治怎么想:$2^k\times2^k$ 的棋盘有一个特殊方格,用 L 形骨牌(盖 3 格)盖住其余所有方格。把棋盘分成 4 个 $2^{k-1}\times2^{k-1}$ 的子棋盘:特殊方格所在的子棋盘直接递归;另外 3 个子棋盘,在 四块合拢处…
- 汉诺塔的分治思想和移动次数:把 n 个盘从 A 移到 C(借助 B):先把上面 $n-1$ 个盘从 A 移到 B,再把最大盘移到 C,最后把 $n-1$ 个盘从 B 移到 C。移动次数 $T(n)=2T(n-1)+1$,$T(1)=1$,解得 $T(n)=2^n-1…
- 最近点对问题的分治怎么设计:按 x 坐标把点集分成左右两半,分别求最近距离 $d_1$、$d_2$,令 $d=\min(d_1,d_2)$;跨过分割线的点对,只需在 距分割线 d 以内的带状区域 里找,把带内的点按 y 坐标排好序,每个点只和排在它后面的常数个点比较…
- 二分搜索为什么也算分治:二分搜索也有分、治、合三步:分,取中点 mid;治,比较 $A[mid]$ 与 x,只在 其中一半 里继续找;合,不需要合并,子问题的答案就是答案。规模每次减半,$T(n)=T(n/2)+O(1)$,所以是 $O(\log n)$。 例 …
- 线性时间选择怎样找第 k 小:用快速排序的划分:取一个枢轴划分后,设枢轴左边有 s 个元素;$k\le s$ 到左边找第 k 小,$k=s+1$ 时枢轴就是答案,否则到右边找第 $k-s-1$ 小。 只递归一侧 ,随机取枢轴时期望时间 $O(n)$,最坏 $O(n^2…
贪心法:选对策略并证明它
- 活动安排问题的贪心策略是什么:把活动按 结束时间从小到大 排序,依次选择第一个与已选活动不冲突(开始时间不早于上一个已选活动的结束时间)的活动。时间主要花在排序,$O(n\log n)$。 例 活动(开始,结束):(1,3)、(2,5)、(4,6)、(5,8)、(6,…
- 分数背包为什么能用贪心,0-1 背包为什么不行:分数背包(物品可以只取一部分)按 单位重量价值 从高到低装,最后装不下的那件取一部分,结果一定最优;0-1 背包的物品不可分,这样装可能不是最优。 例 容量 10,物品(重量,价值):A(6,30)、B(5,22)、C(5,22),单位价…
- 哈夫曼、最小生成树、Dijkstra 的贪心选择各是什么:这些经典算法都是贪心,贪心选择各不相同:哈夫曼——每次合并 当前权最小的两棵树 ;Prim——每次选连接已选顶点集与其余顶点的最小权边;Kruskal——每次选 不成环 的最小权边;Dijkstra——每次确定当前距离最小的未确定顶点。 …
- 区间选点与区间覆盖的贪心键有什么不同:区间选点和区间覆盖的贪心键不同。选点(最少的点,每个区间至少含一个):按 右端点从小到大 排序,当前区间不含已选的最后一个点时,选它的右端点。覆盖(最少的区间盖住目标线段):每次在起点不超过已覆盖位置的区间里,选 右端点最远 的。 例 区…
- 最优服务次序问题怎么贪:一个服务窗口依次为 n 位顾客服务,服务时间为 $t_i$,要使 平均等待时间 (这里指每位顾客从开始排队到自己服务完成的时间)最小:按服务时间从短到长安排。 例 服务时间 5、2、8、1:按原顺序,各人等到服务完成的时间为 5、7、15…
- 删数问题(删去 k 位使剩下的数最小)怎么贪:每次从左向右找 第一个比后一位大的数字 并删掉它(找不到就删最后一位),重复 k 次。 例 2519436,删 3 位:5 比后面的 1 大,删 5 得 219436;2 比 1 大,删 2 得 19436;9 比 4 大,删 9 得 1…
- 找零问题什么时候贪心是对的:面值系统是 1、5、10、25 时,每次取不超过剩余金额的最大面值,硬币数最少;面值任意时贪心 可能出错 。 例 面值 1、3、4,凑 6:贪心取 4+1+1,共 3 枚;最优是 3+3,共 2 枚。 易错 面值系统 1、5、10、25 …
- 贪心算法的正确性怎么证明:常用 交换论证 :设 $O$ 是某个最优解,把 $O$ 里的某个选择换成贪心的选择,证明得到的解仍可行且 不比原来的最优解差 ;这样存在含贪心第一步的最优解,再对剩下的子问题归纳。 例 活动安排:设最优解的第一个活动是 $a_k$,贪心选…
- 各类贪心题分别按什么排序:排序键就是 贪心策略的化身 : 活动安排:按结束时间从小到大 区间选点:按右端点从小到大 分数背包:按单位价值从大到小 最优服务次序:按服务时间从小到大 哈夫曼编码:不排序,用最小堆每次取两个最小的权 易错 排序键选错 是贪心题里典型的错…
- 为证明贪心策略不对,反例该怎么写:好反例要 小、可手算、同时给出两个解 :数据尽量少,写出按这个贪心策略得到的解和更优的解,并比较两者的值。 例 要证明「活动安排按持续时间最短优先」不对:活动 (1,5)、(4,6)、(5,10)。按最短优先先选 (4,6),另外两个都与…
动态规划的写法:状态、转移与边界
- 动态规划的解题步骤是什么:常写成五步:①分析最优解的结构,确认有最优子结构;② 定义状态 ;③写出 转移方程 (用更小的状态表示当前状态);④确定边界;⑤确定填表顺序和答案在表里的位置。教材里更常见的是四步说法:刻画最优解的结构、递归定义最优值、自底向上计算最优值…
- 状态怎么定义才容易写转移:状态要刻画 子问题的规模和约束 :序列问题常用「前 i 个元素」或「以第 i 个元素结尾」,两个序列用 $dp[i][j]$ 表示 X 的前 i 个与 Y 的前 j 个,背包要多一维「容量」。定义不同,转移不同。 例 最大子段和:若定义 …
- 自底向上填表与带备忘录的递归有什么区别:两者都让每个子问题只算一次:自底向上按依赖次序 填表 ,没有递归开销;备忘录法是 递归加记录 ,只算真正用到的子问题。 区分 所有子问题都要算时,自底向上更快;只有一部分子问题会用到,或者填表顺序难确定时,备忘录写起来更省事。 例 $F(…
- 动态规划的填表顺序怎么确定:原则是 先算被依赖的 :$dp[i][j]$ 依赖 $dp[i-1][j]$、$dp[i][j-1]$、$dp[i-1][j-1]$ 时,按行从上到下、每行从左到右;依赖更短区间的(如矩阵连乘),按 区间长度从小到大 。 例 矩阵连乘 $…
- 怎样从 dp 表还原出最优解本身:只存最优值不够时,有两种办法:①另开一个数组记录每个状态最优值来自哪个 决策 ,从答案状态 倒着追踪 ;②不另存,从终点按转移方程重新判断当时选了哪个分支。 例 0-1 背包:从 $dp[n][C]$ 出发,若 $dp[i][c]=dp[…
- 滚动数组怎样把空间降下来:当前行只依赖上一行时,可以只保留一行(一维数组),把 $dp[i]$ 的结果直接覆盖在 $dp[i-1]$ 上,空间从 $O(nC)$ 降到 $O(C)$。 条件 0-1 背包用一维数组时,容量要 从大到小 遍历: for(c=C;c>=…
- 动态规划的时间复杂度怎么算:总时间等于 状态个数乘每个状态的转移代价 (再加上预处理)。 例 最长公共子序列:状态 $m\times n$ 个,每个状态 $O(1)$,总 $O(mn)$;矩阵连乘:状态是区间 $(i,j)$,约 $n^2/2$ 个,每个枚举分割点 …
动态规划的经典模型
- 最大子段和的动态规划怎么写:令 $b[j]$ 为 以第 j 个元素结尾 的最大子段和,则 $b[j]=\max(b[j-1],0)+a[j]$,边界 $b[0]=0$(即 $b[1]=a[1]$),答案是所有 $b[j]$ 中最大的,时间 $O(n)$。 例 $a=…
- 最长上升子序列的动态规划怎么写:令 $f[i]$ 为 以第 i 个元素结尾 的最长严格上升子序列的长度:$f[i]=1+\max\{f[j]\mid j\lt i,\ a[j]\lt a[i]\}$,没有满足条件的 j 时 $f[i]=1$;答案是 $\max f[i]…
- 最长公共子序列的动态规划怎么写:令 $c[i][j]$ 为 X 的前 i 个字符与 Y 的前 j 个字符的最长公共子序列长度:$x_i=y_j$ 时 $c[i][j]=c[i-1][j-1]+1$,否则 $c[i][j]=\max(c[i-1][j],\,c[i][j-…
- 编辑距离的动态规划怎么写:令 $d[i][j]$ 为把 X 的前 i 个字符变成 Y 的前 j 个字符的最少操作数(插入、删除、替换各算 1 次):$d[i][j]=\min(d[i-1][j]+1,\ d[i][j-1]+1,\ d[i-1][j-1]+\del…
- 0-1 背包的动态规划怎么写:令 $dp[i][c]$ 为只考虑前 i 件物品、容量为 c 时的最大价值:$dp[i][c]=\max(dp[i-1][c],\ dp[i-1][c-w_i]+v_i)$(第二项要求 $c\ge w_i$),边界 $dp[0][c]=0…
- 完全背包与 0-1 背包的转移差在哪:完全背包每种物品 可取无限件 :一维写法的转移与 0-1 背包相同, dp[c]=max(dp[c],dp[c-w]+v) ,差别只在容量的 遍历方向 :完全背包从小到大,同一物品可以反复用;0-1 背包从大到小,每件至多用一次。 例 容…
- 硬币兑换(最少硬币数)的动态规划怎么写:令 $f[x]$ 为凑出金额 x 所需的最少硬币数:$f[x]=\min_{c_k\le x}f[x-c_k]+1$,边界 $f[0]=0$,凑不出的置为无穷大。时间 $O(nx)$,n 为面值种数。 例 面值 1、3、4,金额 6:$f…
- 矩阵连乘的最优加括号怎么用动态规划:矩阵链 $A_1,\dots,A_n$,$A_i$ 的维数为 $p_{i-1}\times p_i$。令 $m[i][j]$ 为算出 $A_i\cdots A_j$ 的最少数乘次数:$m[i][i]=0$,$m[i][j]=\min_{i…
- 网格路径最大和的动态规划怎么写:从左上角走到右下角,每步只能向右或向下,求路径上数字之和的最大值。令 $dp[i][j]$ 为走到 $(i,j)$ 的最大和:$dp[i][j]=a[i][j]+\max(dp[i-1][j],\,dp[i][j-1])$;第一行、第一列…
回溯法与分支限界法
- 回溯法的解空间树有哪两种常见形状:常见两种形状。子集树:从 n 个元素里选子集,每个元素「 选或不选 」两种,叶子数 $2^n$,如 0-1 背包、子集和;排列树:n 个元素的 全排列 ,叶子数 ${n!}$,如旅行商、列号取自排列的 n 皇后写法。 条件 搜索时间的上界…
- 回溯法的递归框架怎么写:void Backtrack(int t){ if(t>n){ 记录解; return; } for(每个可选值 x) if(满足约束){ 做选择 x; Backtrack(t+1); 撤销选择 x; } } 步骤 ①处理第 t 层;②t…
- n 皇后问题的约束条件怎么写:按行放置,第 t 行的皇后放在第 $x[t]$ 列。与前面第 k 行($k\lt t$)的皇后不冲突的条件:不同列 $x[k]\ne x[t]$,且不在同一对角线 $|x[k]-x[t]|\ne t-k$。 例 4 皇后恰有 2 个解,列…
- 0-1 背包的回溯法怎样用上界剪枝:物品按单位价值从大到小排序。第 t 层决定放不放第 t 件:放,要求装得下;不放,用 上界函数 判断值不值得继续:上界 = 当前价值 + 剩余物品按分数背包装满剩余容量的价值,不大于当前最优值就剪掉。 例 容量 10,物品 (6,30)、…
- 图的 m 着色问题的解空间树有多大:给 n 个顶点依次着 m 种颜色,相邻顶点不同色。解空间树是 m 叉树 ,深度 n,叶子 $m^n$;回溯时第 t 个顶点只尝试与已着色邻居都不同的颜色。最坏时间 $O(m^n\cdot n)$。 例 三角形(3 个顶点两两相连)用 2 …
- 子集和问题的回溯法怎么剪枝:给定 n 个正整数和目标 M,求和恰为 M 的子集。按顺序决定每个数选不选,用两个剪枝条件:当前和 已超过 M ,剪掉;当前和加上剩余所有数的总和 仍小于 M ,剪掉。 例 集合 {3,5,6,7},$M=15$:选 3、5 后和为 8,…
- 分支限界法和回溯法有什么区别:两者都在解空间树上搜索并剪枝,区别在 搜索方式和目标 :回溯用深度优先,常求所有解或可行解;分支限界用广度优先(队列)或最小代价优先(优先队列)扩展活结点,常求一个最优解,每个活结点只有一次机会生成它的所有孩子。 区分 限界函数在最大化问…
- 排列树的递归框架怎么写:排列树用 交换 生成排列:第 t 层让 $x[t]$ 依次与 $x[t..n]$ 中每个元素交换,递归下一层,返回后 换回来 。 void Perm(int t){ int i; if(t>n){ 记录 x[1..n]; return; …
- 分支限界怎样走一遍:以 0-1 背包为例:用一张 活结点表 :每次取出一个活结点扩展,生成它的所有孩子,不可行或界不优于当前最优值的孩子丢掉,其余放入表中;队列式先进先出,优先队列式先取界最优的。 例 容量 6,物品(重量, 价值)(3,12)、(2,6)、(4,10),已按单位…
方法对照:反例、区别与复杂度
- 贪心和动态规划有什么区别:贪心每步只做一个选择、 不回头 ,只留下一个子问题;动态规划对所有可能的选择都求出子问题的最优值,再从中择优。贪心通常更快(排序加一趟扫描),但 必须证明正确 ;动态规划只要问题有最优子结构、转移写对,就能得到最优解,但时间空间更大。 例…
- 分治和动态规划有什么区别:关键看 子问题是否重叠 :分治的子问题互相独立,递归求解即可,列递归式分析(形如 $aT(n/b)+f(n)$ 时可用主定理);动态规划的子问题大量重叠,要存表避免重复,复杂度用「状态数乘转移代价」分析。 例 归并排序的左右两半是不同的数…
- 动态规划和回溯有什么区别:动态规划要求有 最优子结构 和重叠子问题,用表存子问题的最优值,求的是最优值(或一个最优解),时间多为多项式或伪多项式;回溯没有这样的要求,在解空间里搜索,能求 全部解 ,最坏是指数级。 例 0-1 背包:动态规划 $O(nC)$;回溯加…
- 背包的 O(nC) 为什么不算多项式时间:多项式时间指 输入长度 的多项式。容量 C 用二进制写入,只占约 $\log_2 C$ 位,所以 $O(nC)$ 对输入长度来说是指数级,称 伪多项式时间 。 例 $C=2^{20}$ 时,写下 C 只要 21 位,表格却有 $n\tim…
- 各类算法的典型时间复杂度怎么记:按方法记:分治看递归式,贪心看排序,动态规划看状态数乘转移代价,回溯看叶子数。 分治:归并排序 $\Theta(n\log n)$,Strassen $\Theta(n^{\log_2 7})$,大整数乘法 $\Theta(n^{\log…
本图由 SeekFlaw 编辑团队整理。发现错误,欢迎到学习论坛指出。