动态规划入门
动态规划入门（一）
动态规划(Dynamic Programming)，简称dp，是算法竞赛中一种非常重要的解决问题的手段之一。
一、什么是动态规划
从本质上来说，动态规划就是递推，我们先来看一个有关地推的例子。
例题1、 斐波那契数列
输入\(n\), 求斐波那契数列的第n项
我们在上小学的时候就知道，斐波那契数列的递推式是 \[
f(n) = f(n-1) + f(n-2), f(1) = f(2) = 1
\]
要计算第n项，需要先知道第n-1项和n-2项。要知道第n-1项就要知道n-2和n-3项......直到遇到边界条件f(1)和f(2)。那么反过来说，知道了第1项和第2项，就能知道第3项，第4项及以后。
为什么我要从两种角度说明呢，因为这两种角度正是设计和编写动态规划算法的两种思路和实现方式
第一种角度是从后往前推，用递归实现
1 | int f(int x) { |
上面的代码有一个问题：当n教大的时候，运行时间会非常长。因为其中存在重复计算的问题。比如计算f(6)的时候会需要计算f(5),f(4)。而计算f(5)的时候要计算f(4)和f(3)。其中我们多次重复计算了f(4)。而当n越来越大的时候，重复计算的问题会越来越明显。它的时间复杂度会达到搜索的指数复杂度。如果我们可以在计算完f(4)的时候记住他的答案，等到下次计算的时候就不用再调用递归了，直接返回我们记住的答案就可以了，这会大幅度提升程序运行的速度。在实现动态规划的递归代码的时候，这是不可缺少的。我们称它为记忆化。由于用递归解决问题的方式类似搜索，所以也这种用递归实现的也叫记忆化搜索
1 | int f(int x) { |
第二种角度是从前往后推，用for循环实现
1 | f[1] = f[2] = 1; |
可以看到，for循环实现的代码相比递归的更加简洁，而且本身自带“记忆化”。所以一般我们都会用for循环的递推方式来实现动态规划。
状态转移方程，子结构：
我们再看斐波那契数列的递推式: \[ f(n) = f(n-1) + f(n-2), f(1) = f(2) = 1 \] 这个递推式在动态规划中称作状态转移方程。\(f(n)，f(n-1)，f(n-2)\)是问题的状态。\(f(n)\)这个状态可以由\(f(n-1)\)与\(f(n-2)\)转移过来。因此称它为状态转移方程。在这里，状态f(n)的定义是，斐波那契数列的第n项。而\(f(n-1)\)与\(f(n-2)\)是\(f(n)\)的子结构。因为\(f(n)\)和\(f(n-1)\)，\(f(n-2)\)的问题是相同的，都是求数列的第几项。不同的只是问题的大小。\(f(n)\)比\(f(n-1)\)和\(f(n-2)\)要大。一个问题的解，可以由它的子结构通过状态转移方程转移而来，那么这个问题可以使用动态规划解。而\(f(1),f(2)\)是边界条件，\(f(n)\)是总问题
状态转移方程是动态规划的核心。我们解决一个问题首先就应该思考这个问题的状态转移方程该怎么写
然而，例题1却不是真正意义上的动态规划。通过例子1，我介绍了动态规划的几个关键概念。它最多只能称得上“规划”，而没有“动态”。下面让我们来看一个动态的例子。
例题2、01背包问题
有\(n\)个物品，第i个物品的价值是\(v_{i}>0\)，重量是\(w_{i}>0\)。 你有个容量为\(V\)的背包。每个物品只能拿一次。请问该如何拿才能是背包内物品价值最大化。\(1<=n<=2000,0<=V<=2000\)
这是一个十分典型的动态规划例题。
首先，每个物品只有拿或者不拿这两种选项（这也是01的意思），如果我们已经考虑了\(n-1\)个物品，只剩下最后一个物品了。 我的背包还放得下这个物品，那么我肯定可以拿走它。如果我的背包放不下，那么我就不会选它，我当前背包的价值就是最终的答案。
如果\(f(i, j)\)代表我要选完第\(i\)个物品，我的已经用掉的空间是\(j\)，所得出的总价值。那么有 \[ f(n,j) =max\left\{\begin{matrix}f(n-1,j-w_{i}) + v_{i} \qquad\qquad\qquad (选第n个物品) & & \\ f(n-1,j)\qquad\qquad\qquad\qquad\qquad(不选第n个物品) & & \end{matrix}\right. \] 可以看到，我们在选和不选之间做了一个求最大化的决策。而如果$ f(n-1,j-w_{i}) \(是我选完\)n-1\(个物品后得出的最大价值的状态，并且\)f(n-1,j)\(也是选完\)n-1$个物品后的最大值。（注意：这两个状态是不一样的因为背包容量不一样）。因为最后的状态只会从这两种状态转移而来，那么最后我们总得取一个最大值，那得出的肯定就是全部的最大值了。
然后我们思考状态转移方程。从上面的方程我们可以观察到一件很巧的事情：\(f(n-1,j-w_{i})\) 和 \(f(n-1,j)\) 正是\(f(n,j)\) 的子结构。他们都是从选完某个物品后，背包剩余了某个容量所得出的价值最大值。只是数据的大小不一样。所以，我们可以用相同的策略解决子问题，从而得出子问题的最大值。因为问题是相同的，我们只要把n改成i，就有了状态转移方程： \[ f(i,j) =max\left\{\begin{matrix}f(i-1,j-w_{i}) + v_{i} \qquad,j >= w_{i}\qquad\qquad (选第i个物品) & & \\ f(i-1,j)\qquad\qquad\qquad\qquad\qquad(不选第i个物品) & & \end{matrix}\right. \] 这里我补充了 \(j>=w_{i}\)因为显然，已经用掉的背包容量不可能是负数。然后考虑一下边界条件和问题的解。如果还没有开始选物品，显然价值是0，已经用掉的背包可以大于零（因为可以不使用一部分背包容量）。即边界条件为\(f(0,j)=0\)。总问题的解显然就是\(f(n,V)\)了。
为了便于理解，我们可以画一个状态转移的表格：
比如\(n=3, V = 3。w_{1}=3,v_{1}=2;w_{2}=2,v_{2}=1;w_{3}=1,v_{3}=2;\)
| i | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 |
| 2 | 0 | 0 | 1 | 2 |
| 3 | 0 | 2 | 2 | 3 |
\[ f(0,0)\Rightarrow f(1,0)\Rightarrow f(2,1)\Rightarrow f(3,3) \]
所以最终答案是3。
至此，我们可以写出记忆化搜索的，和for循环版本的代码。
记忆化搜索：
1 | int f(int i, int j) { |
for循环：
1 | for (int i = 1;i <= n; ++i) |
我们观察动态规划的方程与斐波那契数列递推的方程，可以发现，动态规划的方程中，有一个max取最大值的操作。这就是动态规划与递推不同的地方。动态规划在递推的过程中会动态地取最大值，最后得出问题的总最大值。
二、动态规划的步骤
通过背包问题，我们可以总结出，思考动态规划问题的几个步骤
思考问题的状态转移关系，寻找子结构 在这里我们分析了，每个问题的转移性质：每个物品只有拿或者不拿这两种选项。也就是问题从两个状态转移来：选或者不选。接着我们分析了：问题的解可以从它的子结构的最优解转移来。然后我们确定了问题的状态：\(f(i,j)\)表示\(i\)个物品，使用了\(j\)的背包容量得出的最有解。
定义出合适的状态，写出状态转移方程 接着我们就可以写出问题的状态转移方程了，注意这里别补充限制条件。比如某些地方不能出现负数\((j>=w_{i})\)
确定边界条件和最终解的形式 边界条件确定了解最终是从哪个状态转移过来的。找到最终解是哪个状态。
写出代码 递归版的代码和for循环的都可以写。不够对于某些题目，for循环的版本可以进行空间复杂度的优化，所以for循环更普遍。关于优化的技巧，我们将在后续谈到。
三、为什么动态规划是对的
然后是动态规划正确性的证明： 1、对方程正确性的证明 数学归纳：
- 只有\(1\)个物品的时候。容量有\(0~V\)种情况的子问题就是\(f(0,j),0<=j<=V\) 当\(j≥w_{1}\)时答案就是\(v_{1}\)， 否则就是0当
- 选到第\(i\)个物品的时候\(f(i,j)\)这个问题，我们通过转移方程知道，它只会由\(f(i-1,j)\)和\(f(i-1,j-w_{i})\)这两个状态过来，而这两个状态我们已经得到了最优解，那么我从两个里面选一个更优的出来，就是我自己的最优解。 这样从\(1\)开始，依次迭代，最终出来的\(f(n,V)\)一定是最优解
2、对于最优子结构性质的证明：
我需要证明两个性质：
- 性质1、该问题的解只会由子结构转移得来。在这个问题里，\(f(i,j)\)只会由\(f(i-1,j)\)和\(f(i-1,j-w_{i})\)转移来，而且都是这个问题的子结构。证毕。
- 性质2、该问题的最优解，只会由子结构的最优解转移过来。比如对于这道题，\(f(i,j)\)的最优解只会由它的子结构\(f(i-1,j)\)和\(f(i-1,j-w_{i})\)转移过来。我已经计算出来了子结构的最优解，我可以由此算出一个更优的解。假设有另一种情况：问题的解是由子结构的某一个非最优解转移过来得出的最优解。设这个解是\(f(i-1,j)’< f(i-1,j)\)那么根据方程，\(f(i,j)’\)<\(f(i,j)\)矛盾。所以该问题的最优解只会从子结构的最优解转移过来，证毕。
一个问题是否能用动态规划解决，就是看它有没有最优子结构性质。
换句话说，只要一个问题具备了最优子结构性质就可以用动态规划解决。但是却不能用来在一开始判断一个问题是否能用动态规划解决。因为这个判断是基于状态转移方程和子结构来作为基础的。而一个问题可能会有多种状态的定义方式，而有些定义方式是没有最优子结构的性质，有些定义方式是有最优子结构性质的。所以到底一个问题能不能用动态规划来解决，要先尝试后才知道。 所以这个证明方法可以用来判断自己的算法，状态转移方程有没有错误。也就是证明方程正确性的方法。 虽然说没有一个固定的方法判断一个题是否能用动态规划来做，但在做题的时候多多少少都会给一些提示信息，比如数据范围，明显的选择性。 3、关于动态规划证明的推论：
对于一个方程而言，如果它除了子结构部分和上一层有关，其他用到的数据都只与这一层有关，那么在证明完性质1后，性质2也必然正确。举个例子，这个方程里面子结构部分是带有\(f\)符合的\(f(i-1,j),f(i-1,j-w_{i})\)，这一层是第\(i，j\)层。其他用到的数据是\(w_{i},v_{i}\)。于是可以发现，除了子结构部分，其他数据都只与这一层有关。所以性质2是正确的，因为，只要其他数据只与这一层有关，你总可以通过反证法证明出性质2是正确的。 4、动态规划的性质 动态规划和搜索有什么不同之处？ 首先，我提出两个概念：后效性和重叠子结构。
- 后效性是指，这一层的抉择会影响后面状态的抉择。
- 重叠子结构是指，在动态规划的求解过程中，有很多相同的问题会被多次求解。
在搜索中，问题是有后效性。并且几乎没有重叠子结构。
在动态规划中，问题没有后效性。并且有大量重叠子结构。
在背包问题中，我考虑前i个物品的时候，i前面的物品的选择是不会对我第i个物品的选择造成影响的。如果背包问题有依赖性，比如选了某一个物品后，另一个物品就不能选了。这样就会有后效性。因为我不知道前面有没有物品选择过，我这个物品有可能就不具备状态转移方程中“要么选，要么不选”的性质了。那为什么会有重叠子结构呢？不加上记忆化的动态规划就是普通的搜索，它的复杂度是指数级的。也就是它会需要产生指数个子问题需要求解。但这些子问题大部分都是重复的。在搜索的时候做了大量重复的工作。我们可以从方程总知道。一共只有 $ nV $ 种不同的问题需要求解，而通过递推，这些问题都可以在 $ O(1) $ 的时间内解决。所以总的问题复杂度是$ O(n V)$。它使得我们可以在多项式复杂度内求解它。
所以动态规划有以下的性质
最优子结构
无后效性
大量重叠子结构
可以用动态规划解的问题必然具备这几个性质。
四、动态规划方程的多样性
一个问题的方程不一定是一致的。一个问题通过不同的思考角度，可能会有不同的方程。有些方程可以正确解题，而有些却不能。我们还是以上面的背包问题进行举例。
比如状态的定义不同，\(f(i,j)\)表示考虑完第\(i\)个物品后，\(j\)表示剩余的背包容量的最优解。那么可以写出下面的方程 \[ f(i,j)=max \begin{cases} f(i-1,j+w_{i})+v_{i} & \text { , } j+w_{i}<=V \\ f(i-1,j) & \end{cases}\\ 边界条件：f(0,V)=0，最终解： f(n,k) ,0<=k<=V \] 比如\(f(i,j)\) 表示考虑完第i个物品后，j表示剩余背包容量的最优解，但是正着推。 \[ f(i,j)=max \begin{cases} f(i+1,j-w_{i})+v_{i} & \text { , } j>=w_{i} \\ f(i+1,j) & \end{cases}\\边界条件：f(n,k)=0,1<=k<=V,最sf终解：f(0,V) \] 这两个方程都是正确的。但是相比上面给出的方程却不便于编写。具体代码编写留给读者作为练习完成。（注意for循环的方向需要保证子结构先计算好）。
五、空间复杂度优化
观察背包问题的方程的方程： \[ f(i,j) =max\left\{\begin{matrix}f(i-1,j-w_{i}) + v_{i} \qquad,j \geqslant w_{i}\qquad\qquad (选第i个物品) & & \\ f(i-1,j)\qquad\qquad\qquad\qquad\qquad(不选第i个物品) & & \end{matrix}\right. \]
可以发现，\(f(i,j)\)的答案之和\(f(i-1,k)\)有关也就是，只和\(i\)的上一层\(i-1\)，而不需要\(i-2,i-3\)有关。而我们再整个计算过程用二维数组存储了所有的答案。这样是有些浪费空间的。不妨把与计算无关的空间利用起来，可以省去一个维度，这就是所谓的滚动数组。
比较稳妥的方法是使用两行的数组，区分上一行与这一行
1 | int now = 1, pre = 0; // 设置现在要计算的now，和之前的答案pre |
最佳的压缩方式可以直接压缩成一维数组，但此时要特别注意for循环的方向。不能把之后需要计算答案的部分给覆盖了，所以这里第二个for循环需要反过来。如果不反过来的话。那么先计算了\(f(i,0)\) 然后计算\(f(i,5)\)的时候需要用到\(f(i-1,0)\)而此时它已经被覆盖了，此时就会算错。而滚动数组则再压缩的时候不用考虑这个问题
1 | for (int i = 1;i <= n; ++i) |
由于递归的调用不是一层一层的，所以不能进行空间压缩。
动态规划入门（二）——线性DP之背包问题
背包问题分为很多种，其实不止01背包问题。其他的比如完全背包问题，多重背包问题，分组背包问题.......而背包问题的模型思想适用于解决很多问题。
一、完全背包问题
有\(n\)个物品，第i个物品的价值是\(v_{i}>0\)，重量是\(w_{i}>0\)。 你有个容量为\(V\)的背包。每个物品可以拿无限次。请问该如何拿才能是背包内物品价值最大化。\(1\leqslant n\leqslant 2000, 0 \leqslant V \leqslant 2000\)
完全背包问题是01背包问题的一个变种：每个物品数量从只能拿一次，变成了可以拿无限次。在01背包中，我们考虑完了第i个物品后，要去向第i+1个。但是完全背包问题中。我们却不能直接去下一个，而是可能继续考虑当前的。总得来说，当我们考虑第i个物品的时候，我们有2种选择：
- 当背包还有空间的时候，拿走这个物品
- 不拿物品，考虑下一个物品
于是我们可以写出如下的方程： \[ f(i,j)=max \begin{cases} f(i,j-w_{i})+v_{i} & ,j \geqslant w_{i}\\ f(i-1,j) \end{cases} \\ 边界条件:f(0,k)=0 , 0 \leqslant k \leqslant V , 最终解 f(n,V) \] 对应的代码如下：
1 | for (int i = 1;i <= n; ++i) |
我们发现，\(f(i,j)\) 的答案恰好和上一层i和这一层i有关，所以我们可以用滚动数组压缩一个维度
1 | int now = 1, pre = 0; |
如果还要压缩得极限一点，我们可以只使用1个一维数组：
1 | for (int i = 1;i <= n; ++i) |
如果我们把这一段代码和01背包压成一维数组的代码进行比较的话，会发现。除了第二层的for的方向反过来了，其他的都没有边。这是为什么呢？
(留坑待填)
二、分组背包问题
有\(n\) 组物品，每组有 \(s\) 个物品 每组物品只能选 \(1\) 个，第 $ i$ 组第 \(k\) 个物品的价值是\(v_{i,k}>0\)，重量是\(w_{i,k}>0\)。 你有个容量为\(V\)的背包。请问该如何拿才能是背包内物品价值最大化。\(1\leqslant n\leqslant 2000, 0 \leqslant V \leqslant 2000\)
我们先枚举组的方案，然后，对于每一组，有 \(s\) 种选择。那么通过枚举选择可以写出方程: \(f(i,j)\) 表示对于前 \(i\) 组物品, 用了 \(j\) 容量的背包的子问题。 \[ f(i,j)=max \begin{cases} f(i-1,j-w_{i,k})+v_{i,k} & \text { , } j \ge w_{i,k} & 1 \le k \le s \\ f(i-1,j) & \end{cases}\\ \]
例1、金明的预算方案
思路：我们可以把每个主件和它的从属附件看成一个组。那么枚举这个组的所有可能性：
啥也不选
只选主件
选主件和附件1(如果有附件1)
选主件和附件2(如果有附件2)
选主件和附件1和附件2 (如果有附件3)
那么就可以转化成分组背包的模型了。用分组背包来解释就是每组物品有5个(5种选择),每组物品只能选一个.(选一种可能性作为最大值). 所以我们就可以用分组背包来解决它。我们把方程写出来 \[ f(i,j)=max \begin{cases} f(i-1,j-w_{i,0})+v_{i,0}\cdot w_{i,0} & \text { , } j \ge w_{i,0}\cdot v_{i,0} \land 存在主件 \\ f(i-1,j-w_{i,0}-w_{i,1})+v_{i,0}\cdot w_{i,0}+v_{i,1}\cdot w_{i,1} & \text { , } j \ge w_{i,0}\cdot v_{i,0} + v_{i,1}\cdot w_{i,1} \land 存在附件1 \\ f(i-1,j-w_{i,0}-w_{i,2})+v_{i,0}\cdot w_{i,0}+v_{i,2}\cdot w_{i,2} & \text { , } j \ge w_{i,0}\cdot v_{i,0} + v_{i,2}\cdot w_{i,2} \land 存在附件2 \\ f(i-1,j-w_{i,0}-w_{i,1}-w_{i,2})+v_{i,0}\cdot w_{i,0}+v_{i,1}\cdot w_{i,1}+v_{i,2}\cdot w_{i,2} & \text { , } j \ge w_{i,0}\cdot v_{i,0} + v_{i,1}\cdot w_{i,1} +v_{i,2}\cdot w_{i,2} \land 存在附件1,2 \\ f(i-1,j) & \end{cases}\\ \] 如此我们就可以把代码写出来了
1 |
|
例2、排兵布阵
首先发现，如果对某个城市发兵打过了某个玩家 \(i\), 那么对于发兵数量不如他的所有玩家我们都可以打得过。所以我们可以按每个城市的发兵数量排序。然后预处理出打过第 \(i\) 个玩家所可以获得的分数。如果我们可以把城市看做一个组，那么每个城市有 \(s\) 个玩家，就有 \(s\) 种选择，打过第 \(i\) 个玩家，或者不打这个城市。那么我们就可以按照分组背包的思路写出方程。
\(f(i,j)\) 代表攻打前 \(i\) 坐城池，派出 \(j\) 个士兵的收益。\(sol_{i,k}\) 表示攻打第 \(i\) 个城池，第 \(k\) 大派出兵力的玩家派出的兵力。 \(sum_{i,k}\) 代表攻下第 \(i\) 坐城池，派出刚好可以攻下第 \(k\) 大的玩家的兵力所得到的收益。 \[ f(i,j)=max \begin{cases} f(i-1,j-sol_{i,k}*2-1)+sum_{i,k} & \text { , } j \ge sol_{i,k}*2+1 & 1 \le k \le s \\ f(i-1,j) & \end{cases}\\ \]
1 |
|
动态规划入门（三）——其他线性DP模型
一、区间/环形动态规划
例1：石子合并
在一个圆形操场的四周摆放\(N\)堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆。并将新的一堆的石子数，记为该次合并的得分。试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分。\(1<=N<=100\)
可以看到，石子是环形摆放的。如果直接写方程的话，会有后效性，因而无法用动态规划求解。处理环形动态规划的基本方发是：转化成一般的线性动态规划。我们这个环拆成一条线性的链。每堆石子都有可能摆在链的第一个位置。所以枚举N次。对拆出来的每个链，我们都计算一次动态规划，最后综合出一个总的答案。
对于每一条链，我们考虑最后一次合并，一定是只剩下某两堆合并过的石子，然后将他们合并。那两堆石子可以看作是子问题。对于合并某个区间\([i,j]\)之间的石子这个问题，把一个区间\([i,j]\)分成两堆，则一共有\((j-i+1)\)种分发。也就是分成\([i,k],[k+1,j]\)两堆，其中\(i<=k<=j-1\)。
设\(f(i,j)\)是合并区间\([i,j]\)的石子的最大分数，若第\(i\)个石子的分数为\(v_{i}\)。所以它就是分成两个区间合并的最大值，加上从\(i\)到\(j\)石子数量的和。因为两堆合并，把它们的个数都加起来就是总个数了。我们就可以写出状态转移方程： \[ f(i,j) = _{max}\{f(i,k)+f(k+1,j)\} + \sum _{m=i}^{j}v_{m} \text { , }i<=k<=j-1 \\边界条件：f(i,i)=0,最终解：f(1,N) \] 我们可以用前缀和的技巧来求\(i\)到\(j\)的和。这里\(sum[i]\)表示从第一个加到\(i\)个石子的综合。那么\(\sum_{m=i}^{j}v_{m}\) 就是\(sum[j]-sum[i-1]\)了。求解最小值的和求最大值的类似，只是把min改成max而已。下面我们看一下关键代码：
1 |
|
下面是推荐的练习题：
断环成链
[IOI1998]Polygon
1 |
|
二、最长上升子序列
给出\(1\sim n\)的一个序列 \(A_n\)，求它们的最长上升子序列的长度。例如 3 2 1 4 2 5 的最长上升子序列为 1 4 5，长度为3
二分优化
我们用 \(low_i\) 表示长度为 \(i\) 的最长上升子序列的最后一项的最小值。这个 \(low_i\) 一定是单调不减的序列。因为假如 \(low_3 > low_4\) ，就是长度为3的上升序列的最后一项比长度为 4 的上升序列的最后一项还大，也就是这种情况: \(low_3=[1,4,7]\) ,$ low_4=[1,4,5,6]$ 那么可以把\(low_4\) 答案的一部分给 \(low_3\) 使得 $low_3 $ 达到更优解。 \(low_3'=[1,4,5]\) 所以计算好的 \(low_i\) 是单调不减的序列。
对于要求的序列的某个元素 \(A_i\) , 它的每一项有两个选择。
它比当前的最长 \(low_{ans}\) 的值还大，那么就通过把 \(A_i\) 加入 \(low_{ans}\) 的后面构造一个 \(low_{ans+1}\) 的答案
它小于 \(low_{ans}\) 的答案，但是它或许可以更新 \(low_{ans}\) 前面的答案。 因为 \(low_i\) 是单调序列，我们可以二分找到刚好可以比它大的那个 \(low_k\) 然后更新它的值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19int LIS(vector<int> A, int n) { // 严格上升子序列
int ans = 0;
vector<int> low(n+1, oo); // const int oo = 1e9 + 1;
for (int i = 1;i <= n; ++i) {
if (ans == 0 || A[i] > low[ans]) low[++ans] = A[i];
else low[lower_bound(low.begin()+1, low.begin()+ans+1, A[i]) - low.begin()] = A[i];
}
return ans;
}
int LDS(vector<int> A, int n) { // 最长不上升子序列
int ans = 0;
vector<int> low(n+1, oo);
for (int i = 1;i <= n; ++i) {
if (ans == 0 || -A[i] >= low[ans]) low[++ans] = -A[i];
else low[upper_bound(low.begin()+1, low.begin()+ans+1, -A[i]) - low.begin()] = -A[i];
}
return ans;
}
三、最长公共子序列
给出\(1\sim n\)的两个排列\(P1\)和\(P2\)，求它们的最长公共子序列的长度。例如 3 2 1 4 5 和 1 2 3 4 5 的最长公共子序列是 2 4 5，长度为3
设有2个数列 : \[ A_{1},A_{2},A_{3},A_{4},A_{5}...,A_{n}\\B_{1},B_{2},B_{3},B_{4},B_{5}...,B_{n} \] 我们从\(A\)和\(B\)各取任意一个数\(A_{i}和B_{j}\)，那么只有两种情况:
\(A_{i}=B_{j}\) 这种情况下，它可以加在之前的公共子序列上。所以设\(f(i,j)\)是包含\(A_{i},B_{j}\)前面的最长公共子序列的长度是那么我们可以知道 \(f(i,j)=f(i-1,j-1)+1\)。当然，我们也可以选择不加在它上面。于是\(f(i,j)=f(i,j-1);f(i,j)=f(i-1,j)\)。在这三者间我们取个最大值
\(A_{i}\neq B_{j}\) 这种情况下，我们只能从前面的公共子序列转移过来。\(f(i,j)=f(i,j-1);f(i,j)=f(i-1,j)\),并在它们之间取最大值。
于是我们可以写出状态转移方程： \[ f(i,j)=max \begin{cases} f(i-1,j-1)+1 & ,A_{i}=B_{j} \\ f(i,j-1) \\f(i-1,j) & \end{cases}\\ 边界条件:f(0,0) = 0, 最终解: f(n,n) \] 于是我们可以写出代码：
1 | for (int i = 1;i <= n; ++i) |
由于\(f(i,j)\)值只和这一层i和上一层\(i\)有关。所以可以用滚动数组压缩一个维度的空间复杂度，代码如下：
1 | int now = 1, pre = 0; |
nlogn优化
我们可以按照 \(A\) 序列的值，给 \(B\) 序列编号。于是问题就转化成了求 \(B\) 编号的最长不下降子序列即可
1 | int LIS(vector<int> A, int n) { |
动态规划入门（四）——DAG动态规划
另一个动态规划的经典模型是DAG（有向无环图）动态规划。很多问题都可以转换为有向无环图的模型，从而使用动态规划求解最长路来求解原问题。
且看下面这个例子
例1：求DAG的最长路
给定一个图\(G(V,E)\), \(n\)是节点数，\(m\)是边数。每一条边都是有向边并且每个节点\(i\)有个权值\(v_{i}\)，并且图中没有环。求从节点\(1\)到\(n\)的一条路径，使得路径上的点权值和最大。\(1<=n<=100000,0<=m<=500000\)
首先，为什么DAG的求最长路可以动态规划。因为是没有环，所以没有后效性。假设\(f(i)\)表示从\(i\)走到\(n\)的最长路
我们可以写出如下的方程 \[ f(i)=_{max}\{f(v)\}+v_{i} \text { , } (i,v)是一条由i到v的边 \\ 边界条件:f(n) = v_{n},最终解:f(1) \] 当然也可以从终点往起点推，根据问题的不同，不同的设法会有不同的编写难度。但都是正确的。
1 | int f(int x) { |
下面让我们来看几个个转换的例题：
一、通过转换成有向无环图解决依赖关系
很多题目里会给许多“约束条件”。比如选择某物品，或者到某个点的先决条件是XXX。我们可以把诸如此类的约束条件转换成有向无环图的边，来解。
例2：矩形嵌套问题
有\(n\)个矩形，每个矩形可以用两个整数\(a，b\)描述，表示它的长和宽。矩形\(X(a,b)\)可以嵌套在矩形\(Y(c,d)\)中，当且仅当\(a<c,b<d,或者b<c,a<d\)（相当于旋转\(90^{\circ}\)）。例如\((1,5)\)可以嵌套在\((6,2)\)内，但不能嵌套在\((3,4)\)内。求最多的矩形排成一排，使得后一个恰好嵌套在前一个矩形里。
这道题目中的约束条件就是嵌套关系，要选这个矩形必须要先选比它大的矩形。
- 假设矩形\(X\)可以嵌套矩形\(Y\)那么我们可以从\(X\)到\(Y\)建立一条有向边，表示要选Y必须先选X。
- 添加一个超级原点\(S\)。因为可以从任何一个矩形开始，所以我们从\(S\)到每一个矩形建立一条有向边。同样的我们添加一个超级终点\(T\)。因为可以从任何一个矩形结束，所以每个矩形还要通向\(T\)。
- 每个节点有一个权值为1。在寻找路径的时候，假设我们经过了一个点，那么我们加上它的权值1，表示我们选取这一个矩形。那么一条从S到T的路径上所有经过点的路径总和就对应了我们选取矩形的个数。因为走的是有向边，所以每一条路径都是合法的（也就是一个接一个嵌套的）。
- 因为大的矩形不能排在小的矩形后面，所以必然不可能出现环。这样DAG上从S到T的最长路径，就对应了我们要求的最优解。
二、以时间为推移顺序，构造有向无环图
例3：打鼹鼠
在一个\(n \ast n\)的网格中，在某些时刻鼹鼠会在某一个网格探出头来透透气。你可以控制一个机器人来打鼹鼠，如果i时刻鼹鼠在某个网格中出现，而机器人也处于同一网格的话，那么这个鼹鼠就会被机器人打死。而机器人每一时刻只能够移动一格或停留在原地不动。机器人的移动是指从当前所处的网格移向相邻的网格，即从坐标为\((i,j)\)的网格移向\((i-1, j),(i+1, j),(i,j-1),(i,j+1)\)四个网格，机器人不能走出整个\(n\ast n\)的网格。游戏开始时，你可以自由选定机器人的初始位置。
现在知道在一段时间内，鼹鼠出现的时间和地点，请编写一个程序使机器人在这一段时间内打死尽可能多的鼹鼠。
（留坑待填）
三、理论上任何一个动态规划都可以用DAG的有向无环图解释
（留坑待填）
1 | int f(int x, int y) { // 背包问题 |
树形动态规划
有线电视网
1 |
|
树形背包dp
我们以选课这题为例子，因为它非常的经典。它不仅包含了树形01背包的模型，它还是一个有依赖的背包问题。因此这道题有很多种解法，也有很多的地方值得讲一讲。
选课
现在有 \(N\) 门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程 a 是课程 b 的先修课即只有学完了课程 a，才能学习课程 b）。一个学生要从这些课程里选择 \(M\) 门课程学习，问他能获得的最大学分是多少？
$ 1≤N≤300 , 1 M $
最简单的写法 \(O(n^3)\)
首先考虑状态转移方程。首先对于一个问题来说，它如果可以动态规划的话，那么他一定存在最优子结构。也就是说他是存在可以分解的子问题，并且答案是可从这个子问题中转移过来。对于一个树而言，它有一个天然的子问题结构：那就是子树的结构。【什么是子树】也就是说，可以把问题拆解为子树的问题，等子树解决完问题了之后，在和自己合并就可以得出自己的答案了。那么对于这道题而言，它是一个树形的结构。
那么第一个最容易想到的拆分思想就是, 以子树为单位做状态的划分：
假设 \(f(x,j)\) 是当前这个根节点 \(x\) 的子树中选 \(j\) 个节点的最大值。那么对于这个跟节点代表的这门课而言，我们只要两种选择：要么我选这门课，要么我不选这门课。
如果我不选这门课，那么我的价值就是 \(0\) , 因为如果你不选这门课的话，你子树中的课也都不能选。
如果我选这门课，那么我的价值就是在我的子树中选 \(j-1\) 门课的最大价值加上自己的价值。那么怎么表示在子树中选 "j-1" 门课这个动作呢。我们可以枚举子树。如果 \(v\) 是我的子树，然后它选了 \(k\) 个节点。
我们可以从根节点开始考虑，每个先
修课的我可以选或者不选。如果我不选，那么我的子树也不能选。如果我选了，那么我就可以考虑子树选多少个了。
\[ f(x,i, j)=_{max} \{ f(v, v的孩子数, k)+ f(x, i-1, j-k) \} \\ f(x,1,1) = 1 \\ f(x,1,0) = 0 \]
状态压缩dp
宝藏
首先处理出每个状态走1步最多能到的状态。然后枚举每一个状态，然后枚举状态的子集，如果可以扩展，就计算一下最小的距离。
(待填)
1 |
|
动态规划计数
子串
1 |
|
数位dp
可以作为变量的
- 数位之和 一共 9*12 = 110 左右
- 数字的个数
- 是否前导零
首先数字转数位，然后再计算, 模板
1 | ll dp[13][109][109]; |
难题
https://blog.csdn.net/winter2121/article/details/81264324
数位dp
最优子结构的理解：
找出 \(\le x\) 的个数
答案就是 \(x+1\) , 然后我们用数位dp的思想来考虑这件事。
假设 \(x=5674\)
把 \(x\) 存在数组 \(A\) 里面，要倒着存 (不使用0号位)
1 | A = {4, 7, 6, 5} |
设 \(dp(pos,limit)\) 为：构造长度为 \(pos\) 的数字，且之前是否沿着 \(x\) 的边界构造。 \[ \begin{align*} dp(pos,1) &= dp(pos-1,1) + (A[pos]-1)*dp(pos-1,i-1) \\ dp(pos,0) &= 9*dp(pos-1,0) \end{align*} \] 如果沿着边界构造(limit = 1)，那么下一位只能选择不超过 \(x\) 的下一位的数也就是 \([0,A[pos]]\)
如果limit = 0, 那么下一位以及后面的所有位都可以选 \([0,9]\) 中的数字
性质：limit=1 的状态只有 \(len(A)\) 个，如果还有其余状态也要乘上
也就是只有沿着 \(x\) 构造才会出现 limit = 1，而且如果 limit = 1，那么之前所有的limit必定为1
所以可以省略limit这个参数，让limit=1的情况不用记忆化
如果只需要构造位数与 \(x\) 相同的数字，只需要判断一下在第一次的时候从 \(1\) 开始就可以了
1 | int mxnum = limit ? A[k] : 9; |
对于 \(x \le 0\) 的情况要特判，不然转换数字会出错
对于 \(x\) 的位数很大的情况，要使用字符串进行输入
对于要求最大最小值的问题，那么就要用两个边界来dp
1 | ll tl = l; |
wechat
alipay