目录

1 基础算法

1.1 排序

1.1.1 快排

1.1.2 归并排序

1.2 二分

1.2.1 整数二分

1.2.2 浮点数二分

1.3 高精度

1.3.1 加法

1.3.2 减法

1.3.3 高精度乘以低精度

1.3.4 高精度除以低精度

1.4 前缀和&差分

1.4.1 一维前缀和

1.4.2 二维前缀和

1.4.3 一维差分

1.4.4 二维差分

1.5 位运算

1.6 双指针

1.7 离散化

1.8 区间合并

2 数据结构

2.1 链表

2.1.1 单链表

2.1.2 双链表

2.2 栈

2.2.1 普通栈

2.2.2 单调栈

2.3 队列

2.3.1 普通队列

2.3.2 循环队列

2.3.3 单调队列

2.4 KMP

KMP字符串问题：

给定一个字符串S，以及一个模式串P，所有字符串中只包含大小写英文字母以及阿拉伯数字。 模式串P在字符串S中多次作为子串出现。 求出模式串P在字符串S中所有出现的位置的起始下标。

暴力做法：

优化：若已经匹配j的长度，下一个字符不匹配了，可以直接滑动到下个匹配j长度的位置，而不是一个一个字符滑。利用模式串的结构性质可以减少匹配步骤，目标就是找到模式串中最大的后缀=前缀。

2.5 Trie树

用数组去建树时需要注意，[N][26]的第一维度不是树的层数，一维是结点总数，而结点和结点之间的关系（谁是谁儿子）是第二个维度。 比如[0][1]=3, [0]表示根节点，[1]表示它有一个儿子‘b’,这个儿子的下标是3；接着如果有一个[3][2]=8 ; 说明根节点的儿子‘b’也有一个儿子‘c’，这个孙子的下标就是8；这样传递下去，就是一个字符串。随便给一个结点][x][y], 并不能看出它在第几层，只能知道，它的儿子是谁。

2.6 并查集

2.7 堆

2.8 哈希表

2.8.1 哈希表的存储结构

2.8.2 字符串的哈希

2.9 STL容器

2.9.1 顺序性容器

顺序性容器就是将一组具有相同类型的元素以严格的线性形式组织起来

2.9.2 关联式容器

关联式容器每一个元素都有一个键值（key），对于二元关联容器，还拥有实值（value）容器中的元素顺序不能由程序员来决定，有set（集合）和map（映射）这两大类，它们均是以RB-Tree（red-black tree，红黑树）为底层架构。

2.9.3 容器适配器

容器适配器是一个封装了序列容器的一个类模板，它在一般的序列容器的基础上提供了一些不同的功能。之所以称为容器适配器，是因为它是适配容器来提供其它不一样的功能。通过对应的容器和成员函数来实现我们需要的功能

2.9.4 string类

2.9.5 bitset压位

2.10 树状数组

2.11 线段树

2.11.1 不带lazy-tag的线段树

AcWing 246. 区间最大公约数

重要性质：gcd(a,b)=gcd(a,b−a)

在lyd的书里提到的这个性质叫更相减损术，可以推广到多个数的情况。 更相减损术其实是欧几里得算法的一个特例。即gcd(a−nb,b)=gcd(a,b)

有了这个式子说明可以通过维护序列的差分来达到求gcd同样的效果。

比如求(a,b,c)，只需要知道现在a的值，然后知道(b-a,c-b)的gcd，再求一个公约数就行了。

差分就可以把区间加减变成单点加减。可以用没有lazy的线段树来做。

再维护一个差分，做成树状数组或者线段树，用来维护每个数的值。

另：gcd(a,b)=gcd(a,−b)

2.11.2 带lazy-tag的线段树

3 图论

3.1 树和图的存储

3.2 搜索与遍历

3.2.1 DFS

利用剪枝的DFS解决的问题：AcWing 843. n-皇后问题 

n−皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

现在给定整数 n，请你输出所有的满足条件的棋子摆法。

输入格式

共一行，包含整数 n。

输出格式

每个解决方案占 n 行，每行输出一个长度为 n 的字符串，用来表示完整的棋盘状态。

其中 . 表示某一个位置的方格状态为空，Q 表示某一个位置的方格上摆着皇后。

每个方案输出完成后，输出一个空行。

注意：行末不能有多余空格。

输出方案的顺序任意，只要不重复且没有遗漏即可。

数据范围

1≤n≤9

输入样例：

Copy

输出样例：

Copy

参考解答：

第一种搜索顺序

 

3.2.2 BFS

3.3 最短路径算法

3.3.1 dijkstra算法

3.3.2 floyd算法

3.3.3 Bellman-Ford算法

3.3.4 spfa算法

3.4 最小生成树

3.4.1 Prim算法

3.4.2 Kruskal算法

3.5 拓扑排序

3.6 二分图

3.6.1 染色法判别二分图

3.6.2 匈牙利算法求最大匹配

4 数学知识

4.1 质数

4.1.1 判定质数

5 动态规划

5.1 背包问题

5.1.1 01背包

选体积等于j的物品：数字组合

朴素版本

优化版本

5.1.2 完全背包

变1 货币系统ACwing1021

本质是解最大无关向量组个数

题目描述

定义一个 货币系统 ：一共有 种货币，每种货币对应面值为

每种货币可以使用 任意多个，进行线性组合：

为该 货币系统 能够 线性表出 的数值

【注】本题的 线性表出 对于 系数的要求 和 线性代数 中的 线性表出 是不一样的

本题的系数必须是 非负整数！

---

定义：

现给定 货币系统 ，求一个 等价 的 货币系统 ，要求 尽可能最小

分析

种货币，每种货币可以使用 无穷多个

通过这些信息，我们可以初步识别该题目是一个 完全背包 的变种题目

接着我们需要挖掘一下题目里的性质：

学过 线性代数 的同学可以无视这一部分，跳到下面的分割线继续看

研究 货币系统 ，如果存在 可以被 中其他的向量 线性表出：

则 在这个货币系统中是 无效的 (所有线性表示中需要用到的项，都可以用 代替)

因此，我们需要求出 货币系统 的 最大无关向量组，即任意 都不能被其他向量 线性表出

---

如何求向量组 的 最大无关向量组

我们可以利用到 数论 中 埃式筛法 的思想：

对于一个 无效的 元素 ，他只会被 小于 他的元素的 线性组合 表出，满足该要求的 就要被 筛掉

所以我们要先 排序

而我们在做 完全背包 的时候，需要求出所有恰好能被前 个物品选出的体积的方案

即就是在 完全背包 求方案数的过程中，统计那些 初始不能被满足 的物品体积 个数

这就是我们在 AcWing 1021. 货币系统 中所使用的 DP模型

那一题我们求解的是方案数，这题稍微改一下，改成这种方案能否被满足即可，具体如下

闫氏DP分析法

再具体一点的代码实现，我会在代码的 注释 中再具体解释

Code

时间复杂度：

空间复杂度：

其中 是最大物品的体积

注：

• 显式的完全背包转移应该是： 也就是确实要枚举 k（第 i 个物品用几次）。

• 我们实际用的是更简洁的等价式： dp[i][j] = dp[i-1][j] || dp[i][j - v[i]] 右边用的是“同一层 i 的 dp”，这行会把“枚举 k 次”的过程隐含进去。证明方法是把它展开（unroll）几步你就能看出来： dp[i][j] = dp[i-1][j] || dp[i][j - v] = dp[i-1][j] || (dp[i-1][j - v] || dp[i][j - 2v]) = dp[i-1][j] || dp[i-1][j - v] || (dp[i-1][j - 2v] || dp[i][j - 3v])

5.1.3 多重背包

模板题

⭐

下面三道题数据范围不一样

4. 多重背包问题 I - AcWing题库 5. 多重背包问题 II - AcWing题库 6. 多重背包问题 III - AcWing题库

有 N 种物品和一个容量是 V 的背包。

第 i 种物品最多有  件，每件体积是 ，价值是 。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。

输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行三个整数 ，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

输出格式

输出一个整数，表示最大价值。

数据范围

/1000/1000 /2000/20000

/2000/20000

输入样例

输出样例

暴力版本，可解决数量级

二进制优化，可解决数量级

优化过程

思想：

将「每种物品可以取 个」这个限制，转化为若干个不同的 0/1物品，然后使用普通 0/1 背包 DP 求解。

拆分方法：

用二进制拆分数量：

• 把数量 转换成多个物品的件数分别是1, 2, 4, …, , 剩余部分

• 这样这些物品数量加起来等于

• 每个拆出来的物品有自己对应的重量和价值（乘上数量）

例子

假设某个物品：

• 重量 w=3

• 价值 v=5

• 数量 a=13

拆分：

• 1 个（重量 3，价值 5）

• 2 个（重量 6，价值 10）

• 4 个（重量 12，价值 20）

• 剩余 6 个（重量 18，价值 30）

总数=1+2+4+6=13

这样就把原来的多重背包问题转成了相当于 0/1 背包的物品集合，每个拆分单元只能选一次（取 0 或 1 次）。

单调队列优化，可解决数量

详细解释

二维朴素版（便于理解代码）

时间复杂度：O()

空间复杂度：O()

滑动窗口的长度为

code(一维优化)

时间复杂度：O()

空间复杂度：O(v)

和 01背包 的优化类似，观察到 状态转移方程，对于 i 阶段，只会用到 i-1 层的状态

因此可以采用 拷贝数组 或 滚动数组 的写法

拷贝数组写法

滚动数组写法

变1 庆功会（多重背包）

题目描述

一共有 $n$ 种奖品，$m$ 元现金

对于第 $i$ 种奖品，其 价格 为 $v_i$，价值 为 $w_i$，数量 为$s_i$

制定一个购买 方案，使得该方案的总价值 最大

分析

物品个数为 $n$，总体积为$m$，初步识别是一个 背包问题

观察到每个物品有 数量限制，断定该题是 多重背包问题

本题是一道 多重背包 的裸题

本篇题解，只展示 多重背包 的朴素优化和分析，关于 单调队列优化 可以看这篇博客

AcWing 6. 多重背包问题 III【单调队列优化+图示】

不多废话，我们直接上 闫氏DP分析法

闫氏DP分析法

初始状态：f[0][0]

目标状态：f[n][m]

Code(朴素写法)

时间复杂度：$O(n \times m \times s)$

空间复杂度：$O(n \times m)$

朴素优化方式

同 01背包 ，对于第 i 阶段的状态更新只会用到第 i-1 阶段的状态

因此可以采用 滚动数组 或者根据状态更新的顺序，直接压缩成 一维 的优化方式

时间复杂度：$O(n \times m \times s)$

空间复杂度：$O(m)$

一维优化方式

5.1.4 分组背包

例1 机器分配

题目描述

总公司拥有 M 台 相同 设备，准备分给下属的 N 个分公司。

第 i 家公司分到 j 台机器后，所获的的收益为

求一种分配方案，使得总收益最大，输出该方案

分析

本题乍一看很像是 背包DP，为了转换成 背包DP 问题，我们需要对里面的一些叙述做出 等价变换

每家公司 我们可以看一个 物品组，又因为 每家公司 最终能够被分配的 机器数量 是固定的

因此对于分给第 个 公司 的不同 机器数量 可以分别看作是一个 物品组 内的 物品

该 物品 的含义：分给第 个 公司 台机器

该 物品 的体积：

该 物品 的价值：

于是，本题就转换成了一个 分组背包问题

直接上 分组背包 的 闫氏DP分析法

初始状态 ：f[0][0]

目标状态 ：f[N][M]

---

动态规划求状态转移路径

这里我介绍一个从 图论 角度思考的方法

动态规划 本质是在一个 拓扑图 内找最短路

我们可以把每个 状态f[i][j]看作一个 点，状态的转移 看作一条 边，把 状态的值 理解为 最短路径长

具体如下图所示：

对于 点 f[i][j] 来说，他的 最短路径长 是通过所有到他的 边 更新出来的

更新 最短路 的 规则 因题而异 ，本题的 更新规则 是

最终，我们会把从 初始状态（起点）到 目标状态 （终点）的 最短路径长 更新出来

随着这个更新的过程，也就在整个 图 中生成了一颗 最短路径树

该 最短路径树 上 起点 到 终点 的 路径 就是我们要求的 动态规划的状态转移路径

如下图所示：

那么 动态规划求状态转移路径 就变成了在 拓扑图 中找 最短路径 的问题了

可以直接沿用 最短路 输出路径的方法就可以找出 状态的转移

Code

找 最短路径 递归写法

5.1.5 背包问题常见变形

例2 有依赖的背包问题（树形DP）

采用树形DP

题目描述

有 件 物品 和一个 体积 为 的 背包

第 件 物品 的 体积 为 ， 价值 为

每件 物品 有一个 父节点物品 ，如果想选第 件 物品，就必须选他的 父节点

拓扑结构 如下图所示：

如果选择 物品5，则必须选择 物品1 和 物品2。

这是因为 物品2 是 物品5 的 父节点，物品1 是 物品2 的 父节点。

求一个方案，使得该选择的物品合法，总体积不超过 ，且总价值最大

分析

这是一道 背包DP 的 变种题目

根据题设的 拓扑结构 可以观察出每个 物品 的关系构成了一棵 树

而以往的 背包DP 每个 物品 关系是 任意的（但我们一般视为 线性的）

所以，这题沿用 背包DP 的话，要从原来的 线性DP 改成 树形DP 即可

---

然后思考 树形DP 的 状态转移

先比较一下以往 线性背包DP 的 状态转移，第 件 物品 只会依赖第 件 物品 的状态

如果本题我们也采用该种 状态依赖关系 的话，对于节点 ，我们需要枚举他所有子节点的组合 种可能

再枚举 体积，最坏时间复杂度 可能会达到 （所有子节点都依赖根节点）

最终毫无疑问会 TLE

因此我们需要换一种思考方式，那就是枚举每个 状态 分给各个子节点 的 体积

这样 时间复杂度 就是

具体分析如下：

闫氏DP分析法

Code

时间复杂度：

5.2 线性DP

5.2.1 数字三角形模型

变1 摘花生

集合划分时，很重要的划分依据是考虑最后一步

变3 方格取数

5.2.2 最长上升子序列模型

例1 最长上升子序列（LIS）

给定一个长度为 的数列,求数值严格单调递增的子序列的长度最长是多少。

输入格式

第一行包含整数 。

第二行包含 个整数,表示完整序列。

输出格式

输出一个整数,表示最大长度。

数据范围

输入样例:

输出样例:

变1-3 友好城市

题目描述

本题的背景是一个造桥项目，初始给定我们 座打算建造的桥

每座桥有两个参数 和 ，表示该桥一头连接在上岸坐标为的地方，一头连在下岸坐标为的地方

题目要求我们找出一种建桥方案，使得在所有建造的桥不相交的前提下，建造尽可能多的桥

求出该方案的造桥数量

---

具体的情况用文字可能不太好解释，我这里画了一张图方便大家理解

红色虚线表示初始提供的打算建造的桥

我们要找出的方案是在不相交的前提下的最大建桥数量

也就是上面的绿线连接而成的方案

这就是本题的大致意思

题解

我们先想一下暴力怎么做

很容易想到，我们可以枚举所有的方案，然后检查方案是否合法，如果合法就考虑是否能够更新最大值答案

这么做的时间复杂度是 ，而 的数据范围是 ，毫无疑问会超时。

所以，我们就需要找出一些性质进行优化

既然是要暴力枚举，我们可以考虑一个枚举方案，按照上岸的坐标从小到大来枚举

然后我们只需关心下岸的坐标之间有何关系即可

于是，可以轻易发现，上坐标从小到大枚举选择到的桥，其对应下坐标也必然是从小到大的

具体见下图：

蓝色表示该方案按照上坐标从小到大先选出来的桥

红色表示该方案的下一座桥的下坐标不是从小到大的，绿色表示是从小到大的

因此，该方案中，在上坐标排序的情况下，下坐标次序不是从小到大的，则必然不合法（会有相交）

于是，这题就变成了：桥以上坐标从小到大排序后，找出下坐标的最长上升子序列长度

关于如何求最长上升子序列模型的DP，大家可以看一下之前的博客，里面有详细的闫氏DP分析法

Code

我们可以用pair或者struct先把所有的桥存下来，然后按照上坐标排序

再然后，下坐标就构成了一个序列，我们只需找出该序列的最长上升子序列的长度，就求出本题的答案了

变1-4 最大上升子序列和

题目描述

本题定义了一个上升子序列和：对于元素满足从左往右数值递增的次序的子序列的和

我们要求出该序列中最大上升子序列和

题解

该题目定义的最大上升子序列模型与我们熟悉的最长上升子序列模型非常相似

因此我们可以采用最长上升子序列DP模型来分析本题

时间复杂度：

闫氏DP分析法

状态表示 : 考虑前i个元素，以第i个元素结尾的最大上升子序列的方案

状态属性: 最大上升子序列和最大

状态转移: (满足才能转移)

集合划分:

Code:

变1-5 拦截导弹

题目描述

本题给定一个数组 ，让我们求解两个量

1. 该数组的最长不上升子序列

2. 该数组最少能被几个最长下降子序列全部覆盖

样例的图例：

题解

对于第一问不再做过多赘述，关于如何求最长上升子序列模型DP，可以看之前的博客

这里主要说一下第二问的贪心思路及证明

第二题要求我们用最少的最长下降子序列对原数组进行全覆盖

考虑一种贪心方案：

对于第i个数来说，把它加入前 i - 1 个数构成的下降子序列组中，所有结尾元素大于第i个数的数中最小的那个数

证明：（最优解 = 贪心解）

假设存在一个最优解，他在考虑第 i 个数放入的下降子序列组中，选择了贪心解方案的后面的一个位置

具体如图所示：（绿色部分，更新了后为保证递增顺序，交换了和，这一步省略了）

可以观察到，该最优策略使得当前局面差于贪心策略，即能接在范围的子序列少了一个

即贪心解 最优解

同理可证，最优策略在考虑第 i 个数放入的下降子序列组中，选择了贪心解方案的后面的第 个位置

也有结论贪心解 最优解

此外，由于贪心解是合法解，所以必然 贪心解 最优解

于是有 贪心解 最优解

证明：（调整法）

假设存在一种最优策略，不是按照贪心方案进行阶段决策的

则我么可以通过有限次的调整，把最优解调整成贪心解的方案，具体如下图所示

于是，由该决策包容性，得出最优解可以是贪心解。

Code

从前往后做一遍最长下降子序列，同时维护一个数组长度为的单调不减数组

数组 q[N] 中每个元素维护的是当前以 q[i] 结尾的下降子序列

于是，对于第 i 个元素来说，他能插入的到 q[N] 中的哪个下降子序列中，是存在一个二分性质的

由于要求的是下降子序列且 q[N] 是单调不减的

因此对于所有的 w[i] ，必然存在一个边界 j ，满足 且

于是我们就可以用二分来优化找满足性质： 的区间左端点即可

具体代码如下：（此题考的主要是这个贪心，对于前面的DP较为简单，因此不画闫氏DP分析法了）

变1-7 最长上升子序列 II

和例1区别在于N的范围更大

AcWing. 896 最长上升子序列 II

题目描述

给定一个长度为N的数列，求数值严格单调递增的子序列的长度最长是多少。

样例

限制

---

算法1（TLE）

(贪心 + 暴力枚举)

• 贪心思路：较小的数开头的数作为的子序列 比 较大的数作为开头的子序列 更好

• 贪心步骤：
• 开一个数组q[i]，存的是以长度为i的上升子序列中末尾元素最小的数，
• q[]一开始是空集，长度为0
• 遍历每个数x，对于当前数x, 先找到一个最大的小于x的数c感谢@sort：
• 情况1：若找不到c, 扩大q[]的长度并记录当前数x
• 情况2：若找到c, 就存在一个不等式c < x ≤ a < b, 则将x覆盖a的位置

时间复杂度

• 遍历每个数是

• 遍历 q 数组每个数, 找到一个最大的小于当前数x的数c，最坏情况需要枚举所有数

• 因此时间复杂度是

• 由于本题的N = 100000, (10^5)^2 = 10^10 会 TLE

C++ 代码

---

算法2

(贪心 + 二分)

• 基于算法1的单调性：找到一个最大的小于等于当前数的数, 我们可以用 二分 来优化

• 二分的思路：
• 先定义边界，l = 0, r = len, 其中len是q数组的长度
• 然后确定check函数, 可以先找到不等式中c < x ≤ a ≤ b的c
• 通过q[r + 1] = a[i]来将x覆盖a的值
• 同时也要考虑算法1的情况1, 需要扩大q数组的长度
• 即r + 1 > len时, 表示超出了二分边界，这时就要len ++更新q的长度

时间复杂度

• 遍历每个数是

• 遍历q数组每个数, 找到一个最大的小于当前数x的数c

• 因此时间复杂度是

C++ 代码

---

Dilworth定理

求最长上升子序列的长度 和 最小的用不上升子序列覆盖 是对偶问题 可以相互转化

• 把一个数列看成一个偏序集，最长上升子序列是该偏序的最长链，非上升子序列是该偏序的反链。

• Dilworth 定理与其对偶（Mirsky 定理）把“最大链/反链的大小”和“用反链/链分解的最少条数”对应起来。

• 因此：
• 最长上升子序列长度 = 最少用不上升子序列将全序列分解的条数（Mirsky 定理）。
• 最长不上升子序列长度 = 最少用上升子序列将全序列分解的条数（Dilworth 定理）。

变1-10 最长公共上升子序列（LCIS）

闫氏DP分析法：(结合了LCS与LIS的状态表示的方法，可以很直接的发现二者的影子)

状态表示 f[i][j]—集合：考虑 a 中前 i 个数字，b 中前 j 个数字 ，且当前以 b[j] 结尾的子序列的方案

状态表示 f[i][j]—属性：该方案的子序列长度最大

状态转移：

1. 从考虑 a数组 中前 i-1 个数字， b数组 中前 j 个数字 ，且当前以 b[j] 结尾的子序列的方案转移过来：

2. 从考虑 a数组 中前 i 个数字， b数组 中前 k 个数字 ，且当前以 b[k] 结尾的子序列的方案转移过来：

初始状态：f[0][0]

目标状态：f[n][i]

集合划分

Code（朴素版）

时间复杂度：O(n^3)

对于本题的数据规模，毫无疑问会超时

这里贴出代码是方便大家理解这个DP模型，因为接下来的优化，就和DP无关，是一个代码的等价变形优化

Code（优化版）

我们可以观察到，对于第二种状态转移：

每次用到的 状态 都是第 i - 1 个阶段的

因此我们可以用一个变量，存储上一个阶段的能够接在 a[i] 前面的最大的状态值

时间复杂度：

5.2.3 状态机模型

例1 大盗阿福

题目描述

街道上有 家店铺，按照顺序从 到 排好

第 家店铺的财产是

大盗阿福如果偷了第 家店铺，则他不能偷 相邻的店铺，否则会被抓起来

帮助大盗阿福找出一种偷盗 方案，使得获得的 总财产最大

分析

这是一道经典的 线性DP 问题

为何本题可以线性DP求解？

先考虑的问题是，我们能否按照从 到 的 线性顺序 找出 最优解

答案当然是可以的，因为每家店铺在第 i 次被偷和在第 j 次被偷，获得的 价值 是一样的

对于一个 非线形 顺序的最优解，可以通过有限次交换，在保证答案不会减少的情况下，变成 线性顺序

于是我们从前往后 线性DP 即可

考虑如何表示当前的状态？

需要记录的有，当前线性递推到第 i 家店铺，以及对于第 i 家店铺，我们选择 偷 或者 不偷

于是就有了如下的 闫氏DP分析法

闫氏DP分析法

状态表示—属性: 考虑前 i 家店铺，当前第 i 家店铺选择 偷(j=1) 或者 不偷(j=0) 的方案

状态表示—集合: 方案的总价值 最大Max

状态计算:

接下来解释一下这里的状态计算

状态机模型分析

如果要偷第 i 家店铺，则第 i-1 店铺不能被偷：

如果不偷第 i 家店铺，则第 i-1 店铺任意安排：

Code

时间复杂度:

空间复杂度:

初始状态： f[0][0]

目标状态： f[n][0] 和 f[n][1]

滚动数组优化

很多 线性DP 都可以用此类优化，详见 【01背包DP模型+朴素优化】

时间复杂度:

空间复杂度:

例2 股票买卖II

DP + 贪心 双解 （附贪心证明）

一、状态机模型DP解法

我这里直接贴出闫氏DP分析法的思维导图

具体的状态机模型分析如下图:

一共只有种状态:

1. 当前处于未持股状态0：

2. 当前处于持股状态1：

Code:

二、贪心解法

纵然，我们可以用DP搜索出所有的方案数，但是通过观察，我们可以发现本题最优解方案存在一定的性质。

我先贴出测试样例的折线图形式（绿色标出下降，红色标出上升）：

考虑一种方案，在每次上升的前一天购入股票，并在上升后的当天卖出的方案

接下来证明该贪心思路得出的方案即是最优解。

（1）证明贪心解 最优解：

由于贪心解都是取区间长度为 的解，因此假设存在于最优解中的某个区间 的长度

那么会出现一下三种情况：

对应三种情形：最优解选取的区间最终点位于上方、下方、相等。

对于情形一：显然 最优解 < 贪心解

对于情形二：显然 最优解 < 贪心解

对于情形三：毫无疑问，这就是存在于贪心解中的情形，因此 贪心解 = 最优解

得证

（2）证明贪心解 最优解：

这部分无需证明，因为贪心解即是合法解，所以他的方案必定大于等于最优解

Code

变2-1 股票买卖IV

题目描述

给定一个长度为 的数组 ，数组的第 个元素 表示第 天的股票 价格

一次买入一次卖出为一笔 合法交易，且不能同时产生多笔交易（必须在再次购买前出售掉之前的股票）

设计一个方案，使得总 合法交易数 不超过 次，总利润最大

接 股票买卖II 的拓展思考

如果你做过前几版的 股票买卖 可以只看下面这几行的分析

AcWing 1055. 股票买卖 II DP + 贪心 双解 中分析过 第二版 的解法

而本题是 股票买卖 系列的 第四版

在 第二版 上， 额外 限制了 总交易的次数，因此 第二版 中的 贪心思路 不再适用

我们可以在 第二版 的 DP模型 上，额外加上记录 当前交易笔数 的参数即可

原题分析

对于第 天 购入 的股票，当且经当第 天才能 卖掉，获得的 利润 为

由此可知求解 股票交易 问题是一个 线性 的过程，于是我们思考一下能否用 线性DP 进行 状态记录 和 转移

线性DP如何记录当前的状态？

我们以当前递推到的天数，作为 线性DP 的阶段

对于递推到的第 天来说，我们需要记录的信息有：

1. 在完成第 天的决策后，状态是持仓()还是空仓()

2. 在第 天交易完成时，总共完成的 完整 的交易数 (题目规定一次买入一次卖出是一笔 完整的交易)

那么如何利用该状态表示出题设中的状态转移行为呢？

1. 买入行为：k=0 k=1

2. 卖出行为：k=1 k=0

3. 持仓行为：k=1 k=1

4. 空仓行为：k=0 k=0

于是，有了如下的 闫氏DP分析法

闫氏DP分析法

状态表示—集合： 考虑前 i 天的股票，第 i 天的 决策 是 k，且完成的 完整交易数 为 j 的方案

状态表示—属性： 方案的总利润 最大MAX

状态计算：

接下来用 状态机模型 解释一下状态计算

状态机模型DP

1. 第 i 天状态是持仓状态(j=1)，则第 i 天可能产生的行为是 买入行为 或 持仓行为

2. 第 i 天状态是空仓状态(j=0)，则第 i 天可能产生的行为是 卖出行为 或 空仓行为

【注】：卖出行为 会构成一次完整的交易，所以进行该类转移时， j 的参数也要变动

Code

时间复杂度：

空间复杂度：

初始状态:

目标状态:

滚动数组优化

很多 线性DP 都可以用此类优化，详见 【01背包DP模型+朴素优化】

时间复杂度：

空间复杂度：

变2-2 股票买卖V

题目描述

给定一个长度为 的数组 ，数组的第 个元素 表示第 天的股票 价格

1. 一次买入一次卖出为一笔 合法交易，且不能同时产生多笔交易（必须在再次购买前出售掉之前的股票）

2. 卖出股票后，无法在第二天买入股票（冷冻期为1天）

设计一个方案，使得总利润最大

分析

本题是 股票买卖系列 的 第五版，我们可以沿用 第四版 继续做一些改变

与 第四版 相关的 dp 分析 和 状态机模型分析 ，在这里我不会具体展开

想了解 第四版 的，具体可以参考 股票买卖 IV【线性DP+状态机模型DP+滚动数组优化】

在这篇博客里，我有详细的分析

以 线性 的方式 动态规划，考虑第 i 阶段/天 的状态，需要记录的参数有哪些：

1. 第 i 天的 决策状态：
1. (j=0) 当前没有股票，且不处于冷冻期 （空仓）
2. (j=1) 当前有股票 （持仓）
3. (j=2) 当前没有股票，且处于冷冻期 （冷冻期）

注意：这里的 冷冻期 状态，实际意义是指当天卖出了股票，所以 后一天是没法交易

状态机模型分析

1. 如果第 i 天是 空仓 (j=0) 状态，则 i-1 天可能是 空仓 (j=0) 或 冷冻期 (j=2) 的状态

2. 如果第 i 天是 冷冻期 (j=2) 状态，则 i-1 天只可能是 持仓 (j=1) 状态，在第 i 天选择了 卖出

3. 如果第 i 天是 持仓 (j=1) 状态，则 i-1 天可能是 持仓 (j=1) 状态 或 空仓 (j=0) 的状态 （买入）

闫氏DP分析法

状态表示—属性: 考虑前 i 天股市，当前第 i 天的状态是 j 的方案

状态表示—集合: 方案的总利润 最大Max

状态计算:

初始状态：

目标状态：

Code

时间复杂度：

空间复杂度：

滚动数组优化

时间复杂度：

空间复杂度：

思路同 01背包

例3 设计密码（KMP自动机） (有问题)

题目描述

给定一个字符串 ，和一个整数

现需设计一个密码 , 需满足：

1. 的长度是

2. 只包含小写英文字母

3. 不包含子串

求该密码的 方案数，答案对 取模

分析

首先读者需要了解一部分自动机的概念，我推荐一下OI-Wiki的这篇博客 自动机 - OI Wiki

了解自动机是学字符串的基础，之后学习 AC自动机、 KMP 、 后缀自动机SAM 都有很大的帮助

求方案数 的题目难免不会让人想到用 动态规划 来求解

设计一个 合法的密码，从前往后 线性构造 是一个不错的枚举方案

因为如果 当前设计的密码 是合法的话，在他后面添上一个 新字符，可能会导致 新密码不合法 的情况，只有可能是 新密码 的 后缀子串 中出现了

通过 线性构造 的方法，我们只需判断 后缀子串 中是否出现 即可

那么如果我们想用线性DP来求解，应该如何记录当前的状态呢？

首先，毫无疑问是用当前构造的密码长度 作为 线性DP 的阶段

可是如何记录当前的长度为 的字符串的 后缀 与 字符串 的匹配情况呢？

关于 单母串 和 单模式串 的 在线匹配，会自然而然的想到一个 字符串算法 —— 前缀函数与KMP

借用 KMP 的思想，我们可以用参数 来表示当前 母串后缀 与 模式串 匹配的 最大长度

KMP 求前缀函数的 在线性 ，使得我们可以任意枚举第 个字符后，快速获得其 前缀函数值

该 前缀函数值 也就是 状态对应的新的 的值

于是我们就可以利用 来更新 的状态，具体看下面的分析：

自动机模型分析

本题对于不同的 模式串，自动机模型 不同，因此我以 模式串 ababc 举例

先看上面的转移

该转移表示 而发生的转移，也就是枚举的字符 刚好等于 模式串 的第 个字符

于是就会使 最大长度 增加 ，即

然后我再具体分析一下这个状态机里的 状态（其他状态可以类比）

我们枚举下一个添加的字符（即枚举 的字符 ）时：

根据如下转移函数：

对应于本样例就是：

1. 是 ，则最大长度增加一，对应到

2. 不是 ，则根据自动机跳到位置 ，如果 则最大长度增加一，对应到

3. 不是 ，则根据自动机跳到位置 ，如果 则最大长度为0，对应到

闫氏DP分析法

状态表示—集合： 考虑构造一个 长度 为 的密码，且后缀与模式串匹配的 最大长度 为 的方案

状态表示—属性： 方案的总数

状态计算：

Code

时间复杂度：

初始状态：

目标状态：

5.3 状态压缩DP

例题2 最短Hamilton路径

给定一张 个点的带权无向图，点从 标号，求起点 到终点 的最短 Hamilton 路径。

Hamilton 路径的定义是从 到 不重不漏地经过每个点恰好一次。

输入格式

第一行输入整数 。

接下来 行每行 个整数，其中第 行第 个整数表示点 到 的距离（记为 ）。

对于任意的 ，数据保证 并且 。

输出格式

输出一个整数，表示最短 Hamilton 路径的长度。

数据范围

输入样例：

输出样例：

分析

1.本题思路 假设:一共有七个点,用0,1,2,3,4,5,6来表示,那么先假设终点就是5,在这里我们再假设还没有走到5这个点,且走到的终点是4,那么有以下六种情况: first: 0–>1–>2–>3–>4 距离:21 second: 0–>1–>3–>2–>4 距离:23 third: 0–>2–>1–>3–>4 距离:17 fourth: 0–>2–>3–>1–>4 距离:20 fifth: 0–>3–>1–>2–>4 距离:15 sixth: 0–>3–>2–>1–>4 距离:18

如果此时你是一个商人你会走怎样的路径?显而易见,会走第五种情况对吧?因为每段路程的终点都是4,且每种方案的可供选择的点是0~4,而商人寻求的是走到5这个点的最短距离,而4到5的走法只有一种,所以我们选择第五种方案，可寻找到走到5这个点儿之前,且终点是4的方案的最短距离,此时0~5的最短距离为(15+4走到5的距离).(假设4–>5=8)

同理:假设还没有走到5这个点儿,且走到的终点是3,那么有一下六种情况: first: 0–>1–>2–>4–>3 距离:27 second: 0–>1–>4–>2–>3 距离:22 third: 0–>2–>1–>4–>3 距离:19 fourth: 0–>2–>4–>1–>3 距离:24 fifth: 0–>4–>1–>2–>3 距离:26 sixth: 0–>4–>2–>1–>3 距离:17

此时我们可以果断的做出决定:走第六种方案!!!,而此时0~5的最短距离为(17+3走到5的距离)(假设3–>5=5)

在以上两大类情况之后我们可以得出当走到5时: 1.以4为终点的情况的最短距离是:15+8=23; 2.以3为终点的情况的最短距离是:17+5=22; 经过深思熟虑之后,商人决定走以3为终点的最短距离,此时更新最短距离为:22。

当然以此类推还会有以1为终点和以2为终点的情况,此时我们可以进行以上操作不断更新到5这个点的最短距离,最终可以得到走到5这个点儿的最短距离,然后再返回最初的假设,再依次假设1,2,3,4是终点,最后再不断更新,最终可以得出我们想要的答案

2.DP分析: 用二进制来表示要走的所以情况的路径,这里用i来代替 例如走0,1,2,4这三个点,则表示为:10111; 走0,2,3这三个点:1101; 状态表示:f[i][j]; 集合:所有从0走到j,走过的所有点的情况是i的所有路径 属性:MIN 状态计算:如1中分析一致,0–>·····–>k–>j中k的所有情况

代码

例题3 小国王（线性状压DP+滚动数组优化+目标状态优化）

题目描述

在 的棋盘上放 个国王

国王可攻击相邻的 个格子，求使它们 无法互相攻击 的 方案总数

八相邻：

通常意义上的八相邻指的是当前元素的上、下、左、右、左上、右上、左下、右下八个方向

分析

这种 棋盘放置类 问题，在没有事先知道一些特定 性质 的情况下来做，都会想到 爆搜

本题的数据规模，也是向着 爆搜 去设置的

如果我们直接 爆搜，则 时间复杂度 为 是会超时的，因此会想到用 记忆化搜索 来进行优化

考虑一下如何进行 动态规划

由于在第 层放置国王的行为，受到 层和 层以及 层的状态影响

那么我们就可以规定从上往下枚举的顺序，这样考虑第 层状态时，只需考虑 层的状态即可

于是乎我们可以考虑把层数 作为动态规划的 阶段 进行 线性DP

而第 阶段需要记录的就是前 层放置了的国王数量 ，以及在第 层的 棋盘状态

这里先分析一下，哪些 棋盘状态 是合法的，哪些 棋盘状态的转移 是合法的

合法的棋盘状态

如上图所示，绿色方块为摆放国王的位置，红色方块为王的 攻击范围

只要任意王之间只要 不相邻，就是 合法的状态

合法的棋盘转移状态

如上图所示，绿色方块为摆放国王的位置，红色方块为王的 攻击范围

只要任意王的 纵坐标不相邻，就是 合法的转移状态

我们可以用 二进制 来表示当前的状态

怎么用二进制表示状态？

若(state >> i) == 1 则表示在当前状态中，第 个位置放置了国王（下标从 开始）

再举一个简单的例子，见下图：

用二进制表示该状态，就是

于是，就有如下 闫氏DP分析

闫氏DP分析法

状态表示—集合 考虑前 层的棋盘，前 层放置了 个国王，且第 层状态是 的方案

状态表示—属性 方案的总数 $Sum$

状态计算—

其中是枚举的能够与$k$合法存在于相邻行中的所有状态，表示状态 中的国王数量

初始状态：

目标状态：

这样直接做，时间复杂度是 是会超时的

但是我们可以通过预处理所有的 合法状态，以及合法的 相邻转移状态，以及 合法状态 摆放的国王数量

因为虽然状态很多，但是 合法状态 并不多， 合法的转移状态 更不多

Code

滚动数组优化思路

由于第 阶段状态只会用到第 阶段的状态，因此我们可以采用滚动数组来优化空间

只贴上优化的部分

y总的目标状态优化思路

我们可以很轻易的观察到，如果当前层的一个棋子都不摆，即

那么所有 合法的状态 都是该状态的 合法转移状态

翻译成白话就是：只要这层不摆东西，则上一层 只要合法，那一定可以转移到这一层的这个状态

因此我们可以增加一个虚拟的第 n+1 行，状态为 0（不放任何棋子）,即把目标状态设为

该状态表示 考虑前 层的棋盘，前 层放置了 个国王，且第 层什么也没放的方案

根据我们之前提到的 状态转移 可知，该状态会把所有到第 层的 合法状态 都转移到自己身上

这样最后我们就 不需要额外枚举所有的目标状态 了

完整代码如下：

变3-1 玉米田（线性状压DP+滚动数组优化+目标状态优化）

题目描述

给定一个 的 矩阵， 的位置不能放置棋子， 的位置能放置棋子

若在坐标 放置了棋子，则 四相邻 的位置上 不能 放置棋子

求摆放的 方案数，答案对 取模

分析

本题基本类似于上一题 AcWing 1064. 小国王【线性DP+状压DP+滚动数组优化+细节优化】

在本篇中没提及的内容，基本都在上一篇中详细分析了 【很详细!】

本题需要额外处理的，是给定的 矩阵里存在着的不能放置棋子的位置

我们用二进制存储的状态 中，使用 表示在该位置放置棋子， 表示在该位置没有棋子

因此我们可以把矩阵每一层的状态也用二进制来压缩存储，且用 表示该位置能放棋子， 表示不能放

这样，只需把枚举的状态 与这一层的状态 做 & 运算

1. 结果为0，表示 放置棋子 的位置没有与 不能放置棋子 的位置重叠，则该状态 合法

2. 结果为1，表示 放置棋子 的位置与 不能放置棋子 的位置发生重叠，则该状态 不合法

具体如下图所示：

闫氏DP分析法

状态表示—集合 考虑前 层，且第 层状态是 的方案

状态表示—属性 方案的总数

状态计算— 其中是枚举的能够与合法存在于相邻行中的所有状态

Code

这里用了 目标状态优化

有不理解的可以看 AcWing 1064. 小国王【线性DP+状压DP+滚动数组优化+细节优化】 里的内容

滚动数组优化

同上一题思路一样，也可以用滚动数组优化

例4 愤怒的小鸟（状压DP+重复覆盖）

题目描述

给定 个 pig 的坐标，其中第 个 pig 的坐标为

弹弓的坐标是 ，弹弓一次可以发射一条轨迹是抛物线的子弹，并且可以消灭该条抛物线上所有的 pig

求解一个方案，使得弹弓发射的所有子弹可以消灭所有的 pig 且弹弓 发射次数最少

本题的参数 是要求大数据搜索优化的，也就是用 Dancing Links 做的 重复覆盖问题

但这不在本篇题解的讨论范围之内（以后有机会可以更）

分析

首先分析一下我们用弹弓发射的子弹的轨迹有哪些特点：

1. 一条经过原点的抛物线

2. 抛物线的开口朝下

这样抛物线方程就可以设为：

方程中有两个参数 和 ，因此我们可以用具体两个点的坐标来唯一的确定一条 抛物线

参数的计算公式如下：

于是我们就可以预处理出最多 条抛物线，然后用这些抛物线对 点集 进行覆盖即可

用已知两点预处理出来的抛物线一定要满足合法（即）

然后对于两点构成的抛物线，我们还要处理出他穿过的其他的点

这样预处理的时间复杂度就是

---

到此处位置，我们就把问题转化为， 重复覆盖问题 （大家可以用搜索优化 Dancing Links 处理该问题 ）

本题解采用 状态压缩DP 来完成

闫氏DP分析法

状态表示—集合：当前点集覆盖状态为 的方案（是采用二进制压缩存储的点集覆盖状态）

状态表示—属性：方案用的抛物线数量最少

状态表示—计算：

其中 是状态 枚举到新抛物线，并进行覆盖以后生成的新状态

初始状态 ：

目标状态 ：

Code

时间复杂度：

1. 预处理

2. 状压DP

5.4 计数类DP

5.5 数位统计DP

5.6 区间DP

例1 石子合并

题意：合并 N 堆石子，每次只能合并相邻的两堆石子，求最小代价

解题思路：

关键点：最后一次合并一定是左边连续的一部分和右边连续的一部分进行合并

状态表示： 表示将 i 到 j 这一段石子合并成一堆的方案的集合，属性 Min

状态计算（s是前缀和数组）：

（1） 时，

（2） 时， （合并一堆石子代价为 0）

问题答案：

区间 DP 常用模版

所有的区间dp问题枚举时，第一维通常是枚举区间长度，并且一般 len = 1 时用来初始化，枚举从 len = 2 开始；第二维枚举起点 i （右端点 j 自动获得，j = i + len - 1）

模板代码如下：

本题C++代码

补充1：从下往上倒着枚举状态

除了按长度枚举，也可以倒着枚举，因为只要保证每种状态都被提前计算即可

从下往上倒着枚举，可以保证你算dp[i][j]时，dp[i][k]和dp[k + 1][j]一定是被提前计算好的，而从上往下枚举则无法保证这一点。所以我们采用倒着枚举

图解：

补充2：记忆化搜索

如果学过后面的记忆化搜索，那也可以用下面的代码。虽然时间会比递推稍微慢一丢丢，但是呢他的思路比较好写

变1-2 能量项链

题目描述

给定 个能量石，每个能量石有一个二元属性

其中 表示第 个能量石和第 个能量石融合产生的 能量 的其中一个参数

当然 表示第 个能量石和第 个能量石融合产生的 能量 的其中一个参数

魔法石是顺序且环形摆放的，每次可以融合相邻两个魔法石

融合两个能量石 所产生的能量为（题目保证，相邻能量石的参数一致，首尾一致）

融合后左侧魔法石的第一个参数和右侧魔法石的第二个参数合并成为一颗新的 魔法石

具体如下图所示：

求最终把所有石头融合成一个石头时，产生的最大能量值

分析

本题可以把区间长度作为搜索的阶段来进行记忆话搜索，因此我们也可以采用 区间DP 的方式来处理

这题和 环形石子合并 十分相似，但又不尽相同

在 环形石子 中，每个石头只有单一的参数，而本题有两个参数，也就意味着我们需要在细节上做出改变

经过观察我们发现，合并两个石头 的操作就像是矩阵乘法一样，合并完后就变成了

因此我们可以离散的来存储每个参数，具体如下所示：

这样 状态表示 就更新为：当前合并的石子堆的左端石头的左参数是 ，右端石头的右参数是 的方案

这样对应的 初始状态 本来应该是一个有着 二元属性 的石头，现在就变成了长度为 的区间

这样合并区间后，需要记录的新石头的参数也刚好是 区间的两端 对应的参数，如下图所示：

而且这里我们的转移方程也要修改为

以往的 区间DP 我们是把区间 拆分为

因为 同一个石子 只会被合并到 一个石子堆 里

但本题合并魔法石时，分割点 要被分到 左侧石子堆的右端点 和 右侧石子堆的左端点 中

因此，参数 要作为两个区间的共同端点来使用，即 和

此外我们原来只需要合并 个石头，这样转换后就要合并 个石头了

具体分析如下所示：

闫氏DP分析法

状态表示—集合 当前合并的石子堆的左端石头的左参数是 ，右端石头的右参数是 的方案

状态表示—属性 方案的费用最大

状态计算—

初始状态：

目标状态：

本题关于如何解决 环的问题 不做额外阐述，有需要的可以参考之前写的这篇 环形石子合并

Code

时间复杂度：

例2 加分二叉树（记忆化搜索）

题目描述

给定一个含有 个结点的二叉树的 中序遍历 序列中每个节点的 权值

定义一棵 子树 的 分数 为

额外规定 空树 的 分数 为

求一种满足该 中序遍历 的建树方案，使得整棵树的 分数 最大

分析

因为本题是一道与树相关的区间DP，因此本题解采用 记忆化搜索 的思想来分析，抛开常规 动态规划 思路

首先读者需要知道一个二叉树的小常识：

二叉树节点 向下投影，映射成的数组序列就是 中序遍历序列，入下图所示

这也是诱使我们本题采用 区间DP 的一大原因之一（但这篇题解采用 记忆化搜索 思想分析）

借助上图直观的表象，我们发现可以任意的选择 中序遍历 的某一段区间便可生成多棵子树（枚举根节点）

于是我们就会想到 分治 的思想，枚举好根节点后，递归的处理左右区间生成的 最大分数子树

回溯后，利用计算好的子树的分数 相乘，再加上根结点的 权值，就可以得出该方案的 最大分数

而直接递归 搜索 的时间复杂度是 （每次枚举当前区间的根结点，然后递归处理左右区间）

（每次向下层递归时，会确定一个根节点，因此每次少 ）

---

因为在这个递归中，有相当大的计算是去处理的 相同的区间

因此我们不妨采用 记忆化搜索 的形式优化掉这些 重复的搜索

考虑用数组 记录以 为左端点， 为右端点的区间，生成的树的最大分数

这样就会 剪枝 掉相当大的冗余 搜索分支

关于输出方案这里就不做过多阐述了，想了解的可以看一下下面两篇博客

1. 递归写法：AcWing 1013. 机器分配【分组背包+背包DP输出方案—拓扑图分析】

2. 迭代写法：AcWing 12. 背包问题求具体方案【01背包 + 背包DP输出方案

Code（记忆化搜索）

时间复杂度：

---

秉持着详细全面的态度，我这里也贴出 闫氏DP分析法 ，但是关于 DP 就不做分析啦，都是裸的 区间DP

闫氏DP分析法

状态表示—集合 当前以 为左端点， 为右端点的区间作为 中序遍历，生成树的方案

状态表示—属性 方案的分数最大

状态计算—

初始状态： 题设规定只有一个节点的子树分数就是其权值

目标状态：

Code（区间DP）

时间复杂度：

变2-1 棋盘分割（记忆化搜索+二维区间DP）

题目描述

给定一个 的棋盘，棋盘的每个小方格都有一个权值

每次我们可以对棋盘进行一次横或竖切，将棋盘分成两块矩形的子棋盘

分割完一次后，我们可以选择两个子棋盘中的一个再继续递归操作

可以发现题目中给的这个图片，右边这个并不是递归下去做的：他对第一次分割的两个矩形又分别进行了分割（题目要求我们只能保留一个继续分割）

现需要把棋盘按照上述分割方案，分成 块（ 次划分操作）

求一个划分方案，使得各子棋盘的 总分的均方差最小

分析

本题如果用 动态规划 来分析，状态表示要至少开5维，记录分割操作的阶段，以及当前的棋盘状态

我这里直接贴出 闫氏DP分析法

闫氏DP分析法

状态表示 —集合：

当前已经对棋盘进行了 次划分，且 次划分后选择的棋盘是 左上角为 ，右下角为

状态表示 —属性：

划分出来的 个子矩阵的 最小（下面给出了这样定义的原因）

状态计算 ：

这里关于 集合的属性 需要一点变化，直接使用 标准差 作为属性，在进行状态转移的时候不好计算

我们把标准差做出如下变化：

由于 与 的单调性相同，要求 最小，就相当于 最小

而转化为 后，对于子状态，我们就可以直接进行 加法运算 来转移了（原来套着根号很难处理）

---

记忆化搜索

本题有这明显的 分治 引导，即给定一个初始的棋盘，然后我们选择进行分割

分割完后，选择保留一个棋盘，然后对另一个棋盘继续进行分割

直到分割次数达到上限

考虑一下直接递归操作的时间复杂度：

这是一个排列数，计算方法很简单，每轮会使用一条分割线，且每条分割线在一个方案里仅能使用一次

不难发现，递归操作会有很多冗余的重复计算，于是我们可以采用 记忆化搜索 进行优化

表示对棋盘进行了 次划分，且 次划分后选择的棋盘是 左上角为 ，右下角为

这一步分析就有点雷同于上面的 DP 了

---

关于如何枚举矩阵的分割（会的可以直接跳过）

由于我们这里记录矩阵的状态是通过他的 对角顶点 记录的，因此分割是我们也可以通过枚举对角顶点完成分割

如下图所示：

竖着切：

横着切：

Code （记忆化搜索）

由于会频繁地计算某个矩阵的方差，因此我们需要先预处理出前缀和，保证计算方差的时间复杂度为

时间复杂度 ：

我这里 阶段定义 的含义和 y总 是反过来的，读者注意区分两者的不同

例3 凸多边形的划分（区间DP+高精度）

题目描述

给定 个点的 凸多边形 中每个 顶点 的 权值

我们可以把该 凸多边形 划分成 n - 2 个 三角形（三角形不能相交，这样就能保证是 了）

每次划分三角形的 费用 为 三个顶点权值 的 乘积

求一个划分 方案， 方案的 费用总和 最小

---

本题是一个给定的 凸多边形 求 三角剖分 的最小费用方案

很显然一个 凸多边形的剖分方案 并不唯一：

在 选定 多边形中 两个点 后，找出 三角形 的 第三个点 的方案有 个

然后还要分别 划分 他的 左右两块区域

因此我们就会想到用 记忆化搜索 或者 区间DP 来进行处理

记忆化搜索介绍 可以参考这篇 加分二叉树【记忆化搜索思想】

区间DP介绍 可以参考这篇 环形石子合并【区间DP+环形区间问题】

本题解采用 区间DP 的方式进行求解

闫氏DP分析法

状态表示—集合 当前划分到的多边形的左端点是 ，右端点是 的方案

状态表示—属性 方案的费用最小

状态计算—

区间DP 在状态计算的时候一定要 认真 划分好 边界 和 转移，对于不同题目是不一样的

然后本题非常的嚣张，直接用样例的 的点告诉我们答案会爆 和

并且没有 取模 要求，那就只能上 高精度 了

Code

时间复杂度： 区间DP

5.7 树形DP

例1 没有上司的舞会

Ural 大学有 名职员，编号为 。

他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。

每个职员有一个快乐指数，用整数 给出，其中 。

现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。

在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。

输入格式

第一行一个整数 。

接下来 行，第 行表示 号职员的快乐指数 。

接下来 行，每行输入一对整数 ，表示 是 的直接上司。（注意一下，后一个数是前一个数的父节点，不要搞反）。

输出格式

输出最大的快乐指数。

数据范围

输入样例：

输出样例：

分析

参考代码

例2 树的直径

题目描述

给定一个含有 个节点的 树，以及树中每条边的 权值

现需要在树中找出一条 路径，使得该 路径 上所有 边 的 权值之和 最大

分析

这是一道比较经典的 树形DP 题目，我们来一步步来剖析这个问题

我们知道：树上 任意两点 的路径是 唯一 确定的，因此我们可以暴力枚举 起点 和 终点 找出最长路径

如果这样做的话，我们来思考一下时间复杂度：

1. 枚举 起点 和 终点 —

2. 找出两点之间的路径长度 —

这里找出两点之间的路径有很多种做法，预处理 st 表然后倍增求LCA、树链剖分、Link-Cut Tree

但是光是枚举 起点 和 终点，时间复杂度 就直接拉满了，显然这种做法不可取

既然这 条路径不能 一一枚举，那么有什么方式可以把他们 分类枚举 呢？

我们考虑换一种 枚举方式：枚举路径的 起点和终点 枚举路径的 中间节点

我们先讨论一下，对于给定拓扑结构的树里的任意节点，经过他的路径有哪些：

观察我标出的 红色节点，那么经过他的路径有：

1. 以其 子树中的某个节点 作为 起点，以他作为 终点 的 粉色路径

2. 以其 子树中的某个节点 作为 起点，以 子树中的某个节点 作为 终点 的 蓝色路径

3. 以其 子树中的某个节点 作为 起点，以 非其子树的节点 作为 终点 的 橙色路径

对于第 1 种情况，我们可以直接递归处理其子树，找出到当前子树根节点最长的路径长度即可

对于第 2 种情况，我们在处理第 1 种情况时，顺便找出 1 类路径的 次长路径

把 最长 和 次长 拼在一起，就是我们要的第 2 种情况

而对于第 3 种情况，我们可以把它归类为其 祖先节点 的第 种情况，让其 祖先节点 去处理即可

把上述两类路径的分析，用 闫氏DP分析法 写出，就是如下形式：

闫氏DP分析法

状态表示—集合: 以节点 为根的子树中，从子树某个节点到 的最长路为 ，次长路为

状态表示—属性: 路径长度的最大值

状态计算—

Code

时间复杂度：

5.8 记忆化搜索

例题 滑雪

给定一个 行 列的矩阵，表示一个矩形网格滑雪场。

矩阵中第 行第 列的点表示滑雪场的第 行第 列区域的高度。

一个人从滑雪场中的某个区域内出发，每次可以向上下左右任意一个方向滑动一个单位距离。

当然，一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。

下面给出一个矩阵作为例子：

在给定矩阵中，一条可行的滑行轨迹为 。

在给定矩阵中，最长的滑行轨迹为 ，沿途共经过 个区域。

现在给定你一个二维矩阵表示滑雪场各区域的高度，请你找出在该滑雪场中能够完成的最长滑雪轨迹，并输出其长度(可经过最大区域数)。

输入格式

第一行包含两个整数 和 。

接下来 行，每行包含 个整数，表示完整的二维矩阵。

输出格式

输出一个整数，表示可完成的最长滑雪长度。

数据范围

输入样例：

输出样例：

分析

那个人可以从矩形网格滑雪场的任意一点出发 可以上下左右移动 每次只能滑一个单位距离 这个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度

样例解释

参考代码

6 贪心

6.1 区间问题

6.2 哈夫曼树

6.3 排序不等式

6.4 绝对值不等式

例题 货仓选址

在一条数轴上有 家商店，它们的坐标分别为 。

现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。

为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。

输入格式

第一行输入整数 。

第二行 个整数 。

输出格式

输出一个整数，表示距离之和的最小值。

数据范围

输入样例：

输出样例：

6.5 推公式

例题 耍杂技的牛

农民约翰的 头奶牛（编号为 ）计划逃跑并加入马戏团，为此它们决定练习表演杂技。

奶牛们不是非常有创意，只提出了一个杂技表演：

叠罗汉，表演时，奶牛们站在彼此的身上，形成一个高高的垂直堆叠。

奶牛们正在试图找到自己在这个堆叠中应该所处的位置顺序。

这 头奶牛中的每一头都有着自己的重量 以及自己的强壮程度 。

一头牛支撑不住的可能性取决于它头上所有牛的总重量（不包括它自己）减去它的身体强壮程度的值，现在称该数值为风险值，风险值越大，这只牛撑不住的可能性越高。

您的任务是确定奶牛的排序，使得所有奶牛的风险值中的最大值尽可能的小。

输入格式

第一行输入整数 ，表示奶牛数量。

接下来 行，每行输入两个整数，表示牛的重量和强壮程度，第 行表示第 头牛的重量 以及它的强壮程度 。

输出格式

输出一个整数，表示最大风险值的最小可能值。

数据范围

输入样例：

输出样例：

参考代码

证明：

贪心得到的答案≥最优解 → 易知

贪心得到的答案≤最优解:

7 时空复杂度分析