第二章是算法入门，讲了搜索、贪心、DP等等基本算法里的基础部分和简单的数据结构，是为初级篇。

这篇讲搜索、贪心和DP的部分。

多校赛好难。

穷竭搜索

最暴力的算法，完全依靠计算机的算力解题。对于有先后状态的可能解集合，有先根据某个状态的一种可能转移搜索下去的深度优先搜索，和先搜索某个状态的所有可能转移的宽度优先搜索。

递归

递归指在一个函数再次调用该函数。

对于拥有子状态的问题，利用递归的算法可以牺牲时间和空间，换来思路比较清晰的代码。

例如求斐波那契数列可以采用递归，注意递归函数一定要有停止条件

long long fib(long long n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

由于上述代码运行时有参数相同的 fib(n) 被调用了许多次，可以将它先记录下来。这是后面会见到的DP思路。

栈

一个先进后出的数据结构，通过 push 将一个元素进栈，pop 将栈顶的元素取出。C++标准库 <stack> 的栈需要用 stack::top 来获得栈顶的元素，stack::pop 只是移出元素。

栈的性质被用来保存调用函数时的“现场”。调用者的相关数据和参数被push到栈中，被调用的函数处理结束后，记录返回的地址，把栈顶不再使用的数据清除，即可回到调用函数的位置，继续执行之后的语句。

显然规模较大的递归会让调用栈增长到相当高的地步，调用函数的开销不仅占用时间，还会花费很大的栈空间。实际上前例求斐波那契数列的递归算法在 n = 40 时就已经需要很长的时间来完成执行。它的时间复杂度是 $O(2^n)$。

队列

一个先进先出的数据结构。C++标准库的队列在 <queue> 中定义，其中 queue::push、queue::pop、queue::front，分别用来存入、移出、获得元素。

深度优先搜索 DFS

深搜从当前状态的一个可能状态开始不断转移，直到无法转移为止，再从下一个可能状态开始重复。显然这样不断嵌套下去的搜索方法适合用递归实现。

递归可以用来解决规模较小的背包问题。

突然感觉OI Wiki上的好像更全啊。啃完这本考虑去通读一下。（能吗

部分和问题

给定 $n$ 个正整数，判断是否能从中选出若干个数，使它们的和恰为 $k$。

显然暴力一点的做法是从第一个数开始，每个数选择取或不取，一直到最后一个数，此时和为 $k$ 则可以。所有可能都搜完之后还没有遇见可行解，则不行。最差情况是一直搜到最后一种组合都没有可行解，复杂度 $O(2^n)$。在 $n$ 较小的情况下用DFS可解。

大概代码

bool dfs(当前位置, 和) {
  if (到最后一个数)return 和 == k;
  return dfs(下个位置, 和); // 不选当前数
  return dfs(下个位置, 和 + 当前数); // 选当前数
  return false;
}

Lake Counting (POJ 2386)

大小为 $N \times M$ 一个园子积了水。八连通 (有公共顶点) 的积水块被视作连在一起，求园子里共有多少片互相不连通的水洼。

从一个有积水且没被搜过的块开始，深搜连接的块，把搜索到的地方记录一下供后续检查。搜完一次即多一片连接的水洼，直到所有积水处都被搜索过。最差情况每个格子被搜索一次，复杂度 $O(8 \times N \times M) = O(N \times M)$。

考虑到输入的积水情况不需要保留，为了简化判断流程，省去记录表的空间，可以每搜到一块积水就把它换成旱地，直到整片园子没有积水。

宽度优先搜索 BFS

宽搜优先处理当前状态所有可能的“下一步”，“均匀地扩散”到覆盖所有状态。它不需要一次走到头，所以不使用递归来实现。宽搜使用队列来存储将要搜索的状态。

搜索时，宽搜将初始状态入队，此后则不断从队首取出状态，同时将该状态可以转移到的未搜索状态入队，直到找到解或队列为空。由队列的性质可知状态是按照距初始状态由近到远的顺序被搜索的。

迷宫最短路

给定一个矩形迷宫。迷宫由通道和墙壁组成，从一个通道可以走到与它四连通的通道。求出从起点到终点需要走的最短步数。输入保证从起点可以走到终点。

由宽搜的搜索顺序可以发现，如果搜索到了终点，则搜索路径一定是最短的。此处一个状态可以由坐标来描述。

用一张表来标记搜索到的状态。将01标记换成路径长度，这张表同时可以用来记录从起点到该格的最短步数，此时“未搜索”需要用充分大的常数来标记。注意溢出。

大概代码

int bfs() {
  queue<point> q;
  初始化表;
  起点入队;
  记录起点;
  while (!q.empty()) {
    取出前端状态;
    if (该状态是终点) break;
    将该状态可转移到的未搜索状态入队, 同时记录到这些状态的距离;
  }
  return 到终点的距离;
}

如果要记录到终点的路径，只需要在搜索到的状态里标记好它的上一个状态，搜索结束后就可以从终点倒序回到起点。部分情况下最短的路径取决于宽搜时状态入队的顺序。

DFS 和 BFS

深搜和宽搜都可以遍历所有的状态，从能解决问题的角度来看，是可以互相替换的。但是两者各有更高效的利用方向。

对于需要搜索所有状态的问题，深搜需要的空间比宽搜要小。宽搜需要一个队列来存放所有的状态，而深搜只需要系统提供的栈。

对于搜索最短路径的问题，宽搜更有优势。宽搜搜到的第一个解必定是转移次数最少的解，而深搜搜到的第一个解取决于每次转移时的方向。只有对所有的可行解继续遍历一遍，深搜才能给出最近的解。但是也有使用宽搜的转移顺序，同时尽量节约空间的“迭代加深深度优先搜索（ID-DFS）”，在此书的4.5节。

枚举特殊状态

C++ 标准库中提供了一些用来代替简单深搜的函数，比如用next_permutation来对所有元素进行全排列。

一些其他的可行解空间生成可以使用特殊写法，比如用位运算生成 $C_m^k$ 的所有排列，在此书的3.2节。

剪枝

我们有的时候不需要知道所有可行解而只想知道“可不可行”，也有的时候发现穷竭搜索在一个已经不可解的状态下面到处乱搜。对于第一种情况，在搜到第一个解时结束搜索即可省去时间。而第二种情况需要更加精细的剪枝策略。

例如深搜解决部分和问题时，如果各元素都非负，那么一旦和超过了 $k$，后续所有的选择就都不可能把和拉下来，直接结束这部分的搜索就可以省去不必要的时间。

更加难懂的搜索手段在此书4，5节。

栈内存和堆内存
为了保存调用现场，主调函数的所有局部变量都要储存起来，这个储存位置叫做栈内存。而使用 new 和 malloc 获得的内存在堆内存里。
栈内存一经分配则无法扩大，也即函数递归的层数是有极限的。Windows下一般的大小为1MB，通常允许上万次递归。Java可以在执行程序时指定栈大小，C++可以在编译时添加 -Wl,--stack=536870912 分配栈区大小为512MB。
出于减少命名重复和提高耦合度等原因，不推荐使用全局变量，但是对算法竞赛这样规模的代码，大可以为了方便而破戒，也不会带来太麻烦的调试成本。
为了给递归留出空间，巨大的变量可以放在堆上。大变量通常会定义得比数据规模上界再多一点点，给字符串后缀0和1-n下标留点余地。

贪心

可以用贪心解决的问题一般有这样的特点：遵循某个规则，选择每个部分状态最优的转移方向，最终能到达整体的最优解。

硬币问题

有1元、5元、10元、50元、100元、500元面额的硬币若干枚，用来支付 $A$ 元，求最少需要的硬币枚数。输入保证有解。

傻子（无意冒犯，我以前也是~~现在还是~~）才会搜索出所有可行解然后取最小值。显然优先选择大额硬币就能获得总数最少的解。

上例即最简单的贪心解法。它有目的地选择某个转移方向并且相信最终的状态一定是最优解。而之前的深搜和宽搜选择转移方向的策略，只是以“最终能遍历所有方向”为目标。

此题也可以看作一个背包问题。选择一定数量的硬币使最大面额等于 $A$，或者选择 $A$ 面额的硬币使数量最小。背包问题通常的动态规划解法也是遍历了多个可行解，效率上不如贪心。

区间调度问题

有 $n$ 项任务，每项任务在 $s_i$ 时刻开始，在 $t_i$ 时刻结束，对每项工作都可以选择参与与否，但不可中途停止。参与的时间不能重叠，上一项任务开始和和下一项任务结束的时刻相同也是不允许的。给出各任务开始和结束的时刻，求一种选择策略使能参与的工作最多。

贪心的策略有时是比较难找的。这题有几个典型的贪心策略：

在可选任务里选择开始时间最早的
在可选任务里选择结束时间最早的
在可选任务里选择用时最短的
在可选任务里选择与其他任务重叠最少的

仔细思考一下各个策略有没有反例:

~~一个长任务从头到尾覆盖了多个可以连续执行的短任务~~
~~这是对的~~
~~一个短任务和两个更长的任务重叠~~
~~通过多次重复相同起止时间的任务掩盖最优解~~

代码实现上，对所有任务按结束时间排一个升序，记一下当前最后一个结束时间，然后挨个选就可以了。

贪心方法的证明
选取了相同数量的任务时，按贪心算法选取的任务结束时间不会更晚。
若存在更优的方案，则在选择结束后，更优的方案选择的任务比贪心多。设贪心选了 $n$ 个，更优选了 $n + k$ 个，则在都选了 $n$ 个时，贪心结束时间不晚于更优，那么更优的后 $k$ 个任务也可以被贪心选择，贪心并未结束选择。
则可反证不存在更优的方案。

一般做题时，尤其是打比赛做题时，不需要详细的证明来背书，只要能 A 就行了。但拿不准或者 WA 了的时候还是仔细考虑一下吧，虽然不觉得这个情况下能证出来什么东西。

Best Cow Line (POJ 3617)

给定一个字符串 $S$，从空字符串开始构造一个等长的字符串 $T$，以下列任意操作构造：

从 $S$ 的头部删去一个字符，添加到 $T$ 的尾部

从 $S$ 的尾部删去一个字符，添加到 $T$ 的尾部

求字典序最小的 $T$。

首先想到的是比较当前 $S$ 的头尾，把字典序更小的字符加到 $T$ 的尾部。如果遇到相同的字符如何处理？

遇到首尾是相同字符时，为了使较小的字符更早地加入到 $T$ 中，需要比较第二个和倒数第二个字符的大小，直到遇到不同的字符，把较小字符那一侧的首/尾字符加入 $T$。

具体实现，可以用一个字符串和双指针（四指针？），也可以用原字符串和一个翻转的字符串，这样更方便表示。中止条件可以是两个指针相遇，也可以是 $T$ 的长度和 $S$ 相等。

一般情况下，求字典序最小的问题可以使用贪心，也可以在搜索时向最小字符转移。

（这题会卡输出，一行 80 个字符。）

Saruman’s Army (POJ 3069)

直线上有若干点，从中选出一部分点打上标记。对每个点，以它为圆心的一个半径内（包括自己）必须有至少一个被标记的点。给定点的总数和半径，求被标记的点数量的最小值。

这个题面是很精简的模型题，可以用到比如说（直的）城墙上设置望楼，（直的）防线上设置哨塔，（一维的）草坪上设置灌溉器。

这样的最大覆盖题显然要充分利用各个已经标记的点。首先第一个点不用标记，向后走一个半径，遇到的最后一个点打上标记，再从它开始走一个半径，遇到的下一个点，处理方式和第一个点相同，如此一直到走完所有的点。

需要两个循环来让指针向后走。要注意的是循环停止的条件，首先是下标不越界，然后为了直观，走到的距离不大于上一个记录的距离加上半径，之后是指针加减 1 的操作。两个记录，一个是“开始的点”，另一个是打上标记的点。这样一个“圆”覆盖的范围只需要标记一个点。注意边界的处理。

Fence Repair (POJ 3253)

为了准备维修栅栏的材料，需要切割一块很长的木板。不考虑切割损耗，木板的长度正好是所有木料的长度和。切断一块木板的代价为该木板的长度。求最小的总代价。例如将长度 $21$ 的木板切割成 $5、8、8$ 三段的最小代价为 $21 + 13 = 34$。

代价和长度有关，那么一段木料被切出来得越迟，它对代价的贡献就越久。显然我们希望这样的木料越短越好。那么从最后一次切割回溯，每次最短的和次短的拼在一起计入代价，就可以得到最小的代价。这也是一种贪心。

大概实现，每次找出最短和次短，将它们拼合，计入代价，然后将拼回去的木板放到原来的数组里直到剩余木板为 1。这里之前的两个位置已经用过了，可以被新木板覆盖，或者记录一下跳过。更好的做法是拼好之后和数组最后一个元素交换一下，这样遍历的开销会递减，剩余木板的数量也可以当作遍历的停止条件。

霍夫曼编码 (Huffman Code)
由于一条信息中各字符出现的次数不尽相同，用同一长度的编码去表示每个字符，出现次数较少的那些字符难免会引起浪费。霍夫曼编码提供了这样一种编码方式：对于出现多次的字符，用较短的编码表示，而出现次数少的字符可以用长一点的编码。只要解决不同长度编码间的识别问题，这样的编码方式就可以极大地节省空间。事实上，霍夫曼编码是码字长度为整数时最优的编码方案。
显然霍夫曼编码是由各字符频率确定的。利用二叉树构造霍夫曼编码时，将频率最低的两个字符作为子结点合并，它们的频率和为父结点的频率。以父结点为代表，继续参与构造，直到所有的结点都被包含在一棵二叉树里。编码时，从根开始，向右为 0，向左为 1，直到遇到一个字符，所经过的 01 序列就是该字符的霍夫曼编码。这些 01序列可以不加分隔地连在一起，表示整条信息。只要序列没有缺损，就不会出现错误识别的情况。
（这个怎么证明？）

动态规划 (DP)

动态规划，Dynamic Programming，DP，是常考炸的题型。当一个问题的子状态有马尔可夫性时，它可以使用 DP 求解。马尔可夫性指子状态的后续转移概率与且仅与该子状态有关，而与之前的状态和到达该子状态的路径无关。大概是这样。又称无后效性，即一个子状态有最优解后，之后的各种决策不会影响它最优解的效果。通俗一点说，就是可以拿到一个递推公式。当然如果能算出通项的话还是直接代更快。

记忆化搜索与 DP

所谓记忆化搜索，就是记住之前搜索过的状态，在下一次遇到时直接查询搜索历史，减少重复搜索的开销。

01背包

有若干个给定价值和重量的物品，从中选择总重量不超过 $W$ 的物品，使价值和最大。

首先能想到暴搜，对每个物品都向选和不选两个方向转移。大概代码：

// 从search(0, 空包容量)开始
int search(当前物品序号, 当前剩余容量) {
  int res;
  if (没有物品了) {
    res = 0;
  } else if (当前物品放不进去) {
    res = dfs(下一个物品序号, 当前剩余容量);
  } else {
    // 在取和不去当前物品中选最优
    res = max(dfs(下一个物品序号, 当前剩余容量), dfs(下一个物品序号, 当前剩余容量 - 当前物品重量) + 当前物品价值);
  }
  return res;
}

前面已经讲过这类的搜索是 $O(2^n)$ 的，一旦物品稍微多一点就会炸。

为了优化这个算法，先把它的递归树画出来看一下。如果样例不是那么巧，很容易发现部分中间结点拿到了一样的参数，而且之后长出来的子树也是完全一样的。实际含义就是无论之前是怎么取的，当取到同一个物品，且剩余同样的空间时，后续的最优解都是一样的。很容易回推得到出现这样局面的原因是之前有若干个物品，其中一个物品的重量等于其它物品的和。那么把这样的状态记录一下，下次遇到时直接查询结果，就可以大大节约时间。此处只需要一张 $n \times W$ 的表就可以存下所有搜索结果（可能是相当稀疏的），复杂度为 $O(nW)$。注意初始化。

这就是记忆化搜索。

然而，如果不小心写成了这样：

int search(当前序号, 当前容量, 当前总价) {
  int res;
  if (没有物品了) {
    res = 当前总价;
  } else if (当前物品放不进去) {
    res = dfs(下个序号, 当前容量, 当前总价);
  } else {
    // 在取和不去当前物品中选最优
    res = max(dfs(下个序号, 当前容量, 当前总价), dfs(下个序号, 当前容量 - 当前重量, 当前总价 + 当前价值));
  }
  return res;
}

这样多拿参数比较方便剪枝，但是这样拿到同样参数的结点就没了。

上一段代码的每个调用状态都是和之前的状态通过 当前总价 增强了联系。它和上上段代码是什么关系呢？第一段代码尽量剥离了子状态和之前状态之间的关系，只要两个参数一样，后续的解法就是一样的。而第二段代码多了一个参数，这参数暗示了之前可能选择的物品，这样一来就从另一个角度描述了这个状态：具体的选择方案。实际上这题不需要给出方案，也就没必要浪费空间记录到每个状态的路径。两段代码结构很像，但是第一段的 res 记录后续能选择的最大价值，而第二段的记录一直以来能拿到的最大价值，可以写成全局变量。含义几乎是相反的。

接下来我们看一下记录搜索用到的这个表。

记这张表为 $dp[i][j]:=从第 i 个开始挑选总重小于 j 的物品时，可以获得的最大价值$。于是有如下递推关系：

从第 $n$ 个（下标为 $0$ 到 $n - 1$）开始挑选时，总为 $0$。
从第 $i$ 个物品开始挑选
- 如果当前物品超重，则当前可挑选最大价值，和从下一个物品开始挑选是一样的。
- 如果当前物品可选，则当前可挑选的最大价值，是不挑选当前物品，和挑选当前物品两个方向中的最大值。

换到公式来说就是：

$dp[n][j] = 0\\\\[2ex]$ $dp[i][j] = \begin{cases} dp[i + 1][j] & j < w[i]\\\\[2ex] \max(dp[i + 1][j], dp[i + 1][j - w[i]] + v[i]) & (其他情况)\\\\[2ex] \end{cases}$

那么只要把这张表算出来就行了，用不用递归的搜索其实无所谓。随着递推，第一个坐标减小，第二个增大或不变。大概代码：

for (int i = n - 1; i >= 0; --i) {
  for (int j = 0; j <= W; ++j) {
    if (j < w[i]) {
      dp[i][j] = dp[i + 1][j];
    } else {
      dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - w[i]] + v[i]);
    }
  }
}

最后的答案存在从第一个开始挑选重量 $W$ 的位置，就是 dp[0][W]。这显然比递归更加简洁。

改变 DP 数组的定义就可以改变填充 DP 数组的方向。定义 $dp[i + 1][j]:=前i个物品中选择总重j以内的最大总价$ 就可以从左上向右下填充数组。

以上是从递推的角度讨论 DP。如果是从状态转移的角度看，一个当前状态可以通过取和不取向两个状态转移，即“前 $i$ 个中取重量 $j$ 以内”向“前 $i + 1$ 个中取重量 $j + w[i]$ 以内”（取）和“前 $i + 1$ 个中取重量 $j$ 以内”（不取）两个状态转移。其中取的转移需要看能不能装得下。转移过去后是否覆盖目标状态，则是看哪个更大。

为了节省内存，可以尝试压缩空间。注意到每次转移只涉及数组的两行，可以把整个 DP 数组简化到只有两行，通过一个跳转来实现“滚动”填充。这需要 $i$ 的状态完全转移到 $i + 1$。

也可以压成一行。观察填充 $dp[i + 1][j]:=从前i个物品中取不超过j重量的最大总价$ 的代码：

for (int i = 0; i < n; ++i) {
  for (int j = 0; j <= W; ++j) {
    if (j < w[i]) {
      dp[i + 1][j] = dp[i][j];
    } else {
      dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);
    }
  }
}

在装不下当前物品时，没有发生更新而是直接继承上一个状态，能装下当前物品时，则更新到最优解。此时可以发现：滚动数组中“上一行”的某个数据如果仍然是最优解，它的数据是可以被保留到“这一行”的，否则在“这一行”中会被新的最优解替换。那么就可以再砍掉一行：

for (int i = 0; i < n; ++i) {
  for (int j = w; j >= w[i]; --j) {
    dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
  }
}

注意循环方向变了，因为01背包每次转移依赖“上一行”的前项。

01背包 · 大

如果你的背包变得特别大，之前 $O(nW)$ 的复杂度就会出问题。不妨换个思路。以前是同重量取最大价值，现在是同价值取最小重量，那么复杂度会变成 $O(n\sum_i v_i)$。

则定义 $dp[i+1][j]:=前i个物品中挑选价值为j的最小重量$，这样填充结束后，答案就是使 $dp[n][j]\leq W$ 的最大的 $j$。

则前 $i$ 个物品中选总价为 $j$ 的状态由来自两个方向的转移得到：

前 $i-1$ 个物品中选总价为 $j$ 的重量
前 $i-1$ 个物品中选总价为 $j-v[i]$，加上第 $i$ 个的重量

注意初始化时还要引入充分大。

两个方向取最小值覆盖。

当背包容量和全部价值和都相当大的时候就没了。

最长公共子序列 LCS

给定两个字符串，长度分别是 $n$、$m$，求它们最长公共子序列的长度。

Longest Common Subsequence 是经典的字符串问题。

用 DP 解决时可以定义 $dp[i+1][j+1]:=串S的前i子串和串T的前j子串对应的LCS长度$。则两个子串各增一个字符时，新的字符串的 LCS 可能是：

旧 LCS 加上新字符
$S$ 的旧子串和 $T$ 的新子串的 LCS
$T$ 的旧子串和 $S$ 的新子串的 LCS

两个旧子串的长度可以不相等，由此能填充整个数组，复杂度 $O(mn)$。

另一种推公式的方法是从后往前推，先判两个完整字符串，再不断地去掉后缀。

从表的右下角向左上角回溯，每一个使转移方向斜着（加一）的项就是 LCS 里的一项，所以记录一下转移方向就能得到子序列本列。

这个东西可以用来查重。

递推与 DP

DP 基本就是递推。

完全背包 01

$n$ 种给定重量和价值的物品，从中选择总重不超过 $W$ 的物品，使选出的物品总价值最大。每种物品可选任意多件。

首先确定 DP 数组的定义：

$dp[i + 1][j]:=从前i种物品中选择总重量j以内时的最大总价.$

则有递推关系：

前零种和总重零显然是 $0$
设第 $i$ 种选了 $k$ 个
- 第 $i$ 种不可选时，$k=0$
- 第 $i$ 种可选时，从前 $i - 1$ 种扣除 $k \times w[i]$ 的重量，用于选择第 $i$ 种

则前 $i$ 种的最优方案是 $k$ 从 $0$ 一直到装不下为止，所有状态中的最大总价。那么可以写出一个三重循环。

这个算法的最坏情况是，遇到重量为 $1$ 的物品时，$k$ 从 $0$ 一直增长到最多 $W$，加上外面两层循环，复杂度 $O(nW^2)$，不算好。

用解决第一个背包问题的思路，来看一下有没有重复的计算。画一下 DP 数组可以发现，在 $dp[i + 1][j]$ 选 $k \geq 1$ 时描述的状态，和在 $dp[i + 1][j - w[i]]$ 选 $k - 1$ 描述的状态是一样的，再向前推也成立。前一个状态已经达到了最优，那么只需要把它拿过来加上一个 $w[i]$ 就行了（无后效性），毕竟只有这么一个转移的方向，$k$ 从 $0$ 开始的增长就可以简化到 $k = 0$ 或 $k \geq 1$，这和01背包是一个意思。

也可以看书上的数学证明：

$\begin{aligned} &dp[i + 1][j]\\\\[2ex] =&\max\{dp[i][j - k \times w[i]] + k \times v[i] | k \geq 0\}\\\\[2ex] =&\max(dp[i][j],\quad \max\{dp[i][j - k \times w[i]] + k \times v[i] | k \geq 1\})\\\\[2ex] =&\max(dp[i][j],\quad max\{dp[i][j - w[i] - k \times w[i]] + k \times v[i] + v[i] | k \geq 0\})\\\\[2ex] =&\max(dp[i][j],\quad max\{dp[i][j - w[i] - k \times w[i]] + k \times v[i] | k \geq 0\}\quad + v[i])\\\\[2ex] =&\max(dp[i][j],\quad dp[i + 1][j - w[i]] + v[i]) \end{aligned}$

这就是01背包了。如此可以舍去关于 $k$ 的循环，复杂度为 $O(nW)$。可以尝试用一维数组去解。

像01背包一样，也可以只用一维数组来做。注意此处每次转移依赖“这一行”的前项，要更改循环顺序。

完全背包 02

和同学讨论到的另一种经典的完全背包问题：

使用若干种给定面额的硬币搭配出指定总面额。每种面额的硬币不限枚数，求全部方案数。

定义 $dp[i + 1][j]:=使用前i种硬币搭配出总额j的方案数(可取0枚)$，则当允许取当前种的硬币时，总方案数等于“取它”和“不取它”的和，即 $dp[i + 1][j] = dp[i + 1][j - w[i]] + dp[i][j]$。每次更新要用到当前行的前项。

多重部分和

给定 $n$ 种不同大小的正整数，数字 $a_i$ 有 $m_i$ 个。判断是否存在一种选数方案，使选出的数字和恰为 $K$。

DP 数组的定义会影响复杂度。

有这样三种定义：

$dp[i + 1][j]:=前i种数字能否加成j$
$dp[i + 1][j]:=前i种数字加成j的方案数$
$dp[i + 1][j]:=前i种数字加成j时，第i种剩余的个数$

1

要使前 $i$ 种能加成 $j$，则前 $i - 1$ 种要能加成 $j, j - a_i, \cdots j - m_i a_i$ 之一。开循环会有三层，复杂度 $O(K\sum_i m_i)$ ，容易炸。没有看到 $n$ 是因为它在求和里面。

2

和上文选硬币的方法一样。显然 $j < a[i]$ 时是不能选当前的。注意上界是 $\min(K,至今为止所有可选硬币的价值和)$，为了节省时间可以在读入的时候维护一个前缀和。最高复杂度 $O(nK)$。

3

注意不能加成 $j$ 的位置要用 $-1$ 填充。则 $dp[i][j]\geq 0$ 时，$dp[i + 1][j] = m_i$；$dp[i + 1][j - a_i] = k$ 时，$dp[i + 1][j] = k - 1$；$dp[i + 1][j - a_i] \leq 0$ 或 $a_i$ 选不上时，$dp[i + 1][j] = -1$。复杂度 $O(nK)$。

最长上升子序列 LIS

长度为 $n$ 的数列 $a0, a_1, \cdots a{n - 1}$，求它最长上升子序列的长度。

经典字符串题目。

定义 $dp[i]:=以a_i结尾的最长上升子序列的长度$，每次扫描到一个新字符，将它和之前的各字符比较，在比它小的字符里选出数组值最大的，加一作为新字符位置的值。没有更小的字符时，取零加一。同时维护整个数组至今的最大值即可。复杂度 $O(n^2)$。

或者定义 $dp[i]:=长度为i+1的上升子序列中最小的末尾元素$，这样定义的原因是相同长度的子序列，末尾越小，后续更有可能遇到更大字符。如果不存在一个长度的子序列，用充分大填充。显然这个数组除了充分大之外是递增的，可以用二分优化到 $O(n\log n)$。

计数问题的 DP

划分数

有 $n$ 个无区别的物品，将它们划分成不超过 $m$ 组，求出划分方法数。结果对 $M$ 取余。

比如 $4$ 个物品分成 $3$ 组以内，叫 $4的3划分$。注意每组是不分先后的，即 $1+1+2$ 和 $1+2+1$ 是同一种划分。DP 在解计数问题和期望问题时也经常用。

定义 $dp[i][j]:=j的i划分的总数$，则容易想到如果每组不同，则 $j$ 的 $i$ 划分就是先取出 $k$ 个，再计剩下 $j - k$ 的 $i - 1$ 划分，$k$ 从 $0$ 到 $j$。

每组相同时，要考虑重复计算，也不能单纯地把 $k$ 取 $0$ 到一半。考虑新的递推关系：当一个 $n$ 的 $m$ 划分 ${a_i}(\sum_1^m a_i = n)$ 成立时，考察它的每一项。如果各项为正，则它对应一个 $n - m$ 的 $m$ 划分；如果有为零的项，则它至少对应一个 $n$ 的 $m - 1$ 划分。此处“至少”是指推到上一个状态即可。则有以下递推关系：$dp[i][j] = dp[i - 1][j] + dp[i][j - i]$。处理一下边界，可以在 $O(nm)$ 里得到答案。

多重集组合数

有 $n$ 种物品，第 $i$ 种有 $a_i$ 个，不同种之间物品不同，同种之间无法区分。从这些物品中取出 $m$ 个，求取法总数对 $M$ 取余的结果。

比较方便地定义 $dp[i][j]:=从前i种物品中取j个的方案总数(模M)$。则 $dp[i][j]$ 是 $dp[i - 1][j - k]$，$k$ 从 $0$ 到 $\min(j, a_{i - 1})$。直接计算的复杂度是三次，再往回推一项之后合并，如下优化到二次：

$\begin{aligned} & dp[i + 1][j]\\\\[2ex] = &\sum_{k = 0}^{\min(j, a_i)}dp[i][j - k]\\\\[2ex] \stackrel{展开，增减项，分类讨论}{=} & dp[i][j] - dp[i][j - 1 - a_i] + \sum_{k = 0}^{\min(j - 1, a_i)}dp[i][j - 1 - k]\\\\[2ex] = & dp[i][j] + dp[i + 1][j - 1] - dp[i][j - 1 - a_i] \end{aligned}$

注意分类讨论时的越界问题。优化的目的是化成递推。

这篇我好像拖了将近一个月？一做志愿者就废了……

下面讲数据结构。正好这学期也开这门课。

还想着看完这本书之后买块键盘呢……

Hello World.

挑战程序设计竞赛 02 章 01