动态规划

动态规划（dp），说是算法，更是一种思想

核心思想：从简单小问题开始逐渐解决复杂问题

在这个思想下，有很多具体算法：01背包，完全背包，区间dp，等等

具体做三件事：定义状态，初始化，状态转移方程

01背包

任务：

你入室盗窃，面对许多东西。每个东西有重量$w$和价值$v$，你背包容量有限，怎么选择使偷走东西的总价值最大？

分析：

面对每个物品，都要选择拿或不拿，所以叫做01背包

定义状态：设 $f[i][j]$ 为考虑前 $i$ 个物品，背包容量为 $j$ 时的最大价值

初始化：不需要

状态转移方程：$f[i][j] = max(f[i-1][j], v[i]+f[i-1][j-w[i]])$

解释：要么不选第$i$个东西，要么选，选了之后背包容量为$j-w[i]$

代码：

例题：洛谷P1048 [NOIP2005 普及组] 采药

https://www.luogu.com.cn/problem/P1048

for(int i = 1; i <= M; ++i){
    for(int j = 1; j <= T; ++j){
        if(t[i] > j) f[i][j] = f[i-1][j];
        else f[i][j] = max(f[i-1][j], v[i]+f[i-1][j-t[i]]);
    }
}

优化：

$f[i][j]$是二维数组，而每次循环只需要上一次数据，考虑降维（空间节约，时间仍要两层循环）

定义状态：设 $f[j]$ 为背包容量为 $j$ 时的最大价值

初始化：不需要

状态转移方程：$f[j] = max(f[j], v[i]+f[j-w[i]])$

注意从后往前循环，这样用到$f[j-w[i]]$是上一次的结果

优化代码：

for(int i = 1; i <= M; ++i) 
  for(int j = T; j >= t[i]; --j) 
  	f[j] = max(f[j], v[i]+f[j-t[i]]);

二维01背包

任务：

你有一些任务，每个任务 $p$ 都要花费一些时间 $t$ 和钱 $m$ ，你的时间和钱有限，怎样分配使完成的任务最多？

分析：

与01背包相比，只是多了一个约束条件，所以叫二维01背包

三层循环：遍历任务，遍历钱，遍历时间。空间上可以滚动掉一维

定义状态：设 $f[i][j]$ 为总金钱为 $i$，总时间为 $j$ 时的最多任务

初始化：不需要

状态转移方程：$f[i][j] = max(f[i][j], f[i - m[p]][j - t[p]] + 1)$

代码：

例题：洛谷P1855 榨取kkksc03

https://www.luogu.com.cn/problem/P1855

for(int p = 0; p < N; ++p)
    for(int i = M; i >= m[p]; --i)
        for(int j = T; j >= t[p]; --j)
            f[i][j] = max(f[i][j], f[i - m[p]][j - t[p]] + 1);

完全背包

任务：

你进入仓库盗窃，面对许多种东西。每种东西有重量$w$和价值$v$，你背包容量有限，怎么选择使偷走东西的总价值最大？（假设每种东西都有无穷多件）

分析：

设$ f_{i,j}$表示前 $i$ 种物品使用 $j$ 背包容量能获得的最大价值，状态转移方程：

$$f_{i,j}=\max\limits_{k=0}^{k\le \frac{j}{w_i}} (f_{i-1,j-k\times w_i}+k\times v_i)$$

思想为：01背包只考虑拿一件，完全背包需要考虑所有可能的件数。

优化：

换一种思路：

$$f_{i,j}=\max(f_{i-1,j},f_{i,j-w_i}+v_i)$$

思想为：

• 要么不拿，则$f_{i,j}=f_{i-1,j}$

• 要么拿一件试试，则$f_{i,j}=f_{i,j-w_i}+v_i$，注意这里用到的是本层物品遍历的状态。

在空间上也可以滚动掉一维，但时间仍要两层遍历，外层物品遍历，内层背包容量遍历，注意背包容量从前向后遍历。

优化代码：

for(int i=1;i<=N;i++)
	for(int j=w[i];j<=M;j++)
		f[j]=max(f[j],f[j-w[i]]+v[i]);

可以看到它和01背包的代码是很像的，完全背包和 01 背包的区别就在于对背包容量遍历的顺序不同。

练练手？洛谷P1616 疯狂的采药

https://www.luogu.com.cn/problem/P1616

最长上升子序列（LIS）

任务：

给定$n$个整数$A_1, A_2 \dots A_n$，从左到右按顺序选出尽量多的数，组成一个上升子序列，求长度。

分析：

考虑动态规划，定义状态$dp_i$为以$A_i$结尾的最长上升子序列长度，则状态转移方程为：

$$dp_i=max\{0,dp_j|j<i,A_j<A_i\} + 1$$

最终答案为$ max{dp_i} $，总的时间复杂度为$O(n^2)$

练练手？洛谷P1020 [NOIP1999 普及组] 导弹拦截

https://www.luogu.com.cn/problem/P1020

补充： $\text{Dilworth}$定理——将一个序列剖成若干个单调不升子序列的最小个数等于该序列最长上升子序列的个数

找钱

任务：

你有$N$种不同的面额的纸币$m_1,m_2,\dots m_N$，要组合成$M$元，求有几种组合方法。

分析：

考虑动态规划，定义状态$dp[i][j]$是使用前$i$种纸币拼成$j$元的组合方法数，则状态转移方程为：

$$dp[i][j] = \sum_{k=0}^{\lfloor \frac{j}{m_i} \rfloor} dp[i-1][j-k\times m_i]$$

最终答案为$dp[N][M]$。

两层循环：遍历面额，遍历钱。在加上$k$从$0$循环到$\lfloor \frac{j}{m_i} \rfloor$。

初始化：令所有$dp[i][0]=1$。

优化：

考虑在状态转移方程中，在面额循环中，只用到了上层面额的值，考虑空间上滚动掉一维。优化状态转移方程，思想与完全背包相似：

$$dp[i][j]=dp[i-1][j]+dp[i][j-m_i]$$

dp[0] = 1;
for(int i=1;i<=N;++i){
    for(int j=ms[i];j<=M;++j){
        dp[j]+=dp[j-ms[i]];               
    }
}

乘积最大子数组

核心思想：如果当前位置的最优解未必是由前一个位置的最优解转移得到的，要进行分类讨论。

任务：

一个整数数组 nums ，找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

分析：

如果我们用 $f_{\max}(i)$ 来表示以第 i 个元素结尾的乘积最大子数组的乘积，第一次考虑我们会想：

$$f_{\max}(i) = \max_{i = 1}^{n} \{ f(i - 1) \times a_i, a_i \}$$

但这是错误的，当前位置的最优解未必是由前一个位置的最优解转移得到的。所以我们可以根据正负性进行分类讨论。

考虑当前位置如果是一个负数的话，那么我们希望以它前一个位置结尾的某个段的积也是个负数，这样就可以负负得正，并且我们希望这个积尽可能「负得更多」，即尽可能小。如果当前位置是一个正数的话，我们更希望以它前一个位置结尾的某个段的积也是个正数，并且希望它尽可能地大。因此我们维护两个数组：

$$\begin{aligned} f_{\max}(i) &= \max_{i = 1}^{n} \{ f_{\max}(i - 1) \times a_i, f_{\min}(i - 1) \times a_i, a_i \} \\ f_{\min}(i) &= \min_{i = 1}^{n} \{ f_{\max}(i - 1) \times a_i, f_{\min}(i - 1) \times a_i, a_i \} \end{aligned}$$

最长公共子序列

假设字符串 text 1 和 text 2 的长度分别为 m 和 n，创建 m+1 行 n+1 列的二维数组 dp，其中 $dp[i][j]$ 表示 text1 [0:i] 和 text2 [0:j] 的最长公共子序列的长度。

考虑动态规划的边界情况：dp[i][0]=0、dp[0][j]=0

• 当 text1 [i−1]=text2 [j−1] 时，$dp[i][j]=dp[i-1][j-1]+1$
• 当 text1 [i−1] $eq$ text2 [j−1] 时，$dp[i][j]=\max(dp[i-1][j],dp[i][j-1])$

分治？

动态规划跟分治算法很相似,都是将大问题拆分成小问题逐个击破.

想想归并排序，一个由上到下再反过去递归的分治

分治算法的特点：

• 分治算法每次分解出来的子问题是互相独立,不互相影响的.每个子问题都是独立地被求解.

• 分治算法是自顶而下求解的

动态规划和分治算法的差别:

• 动态规划的子问题并不是互相独立,是有交集的.

• 动态规划多数都是自底而上来求解问题的,先解决小问题,再由小问题解决大问题.(即由之前存在过的状态推导出后面的状态)

• 动态规划会将解决过的子问题的结果记忆起来,用于求解更大的问题或者,遇到相同的子问题时不用再次计算,直接在使用记忆的结果即可.

杂题思路

从(0,0)到（m,n）有多少种路径？从A到B，不管其如何走，必然要经过m+n个格子。然后这m+n个格子里面只有两种状态，向上或向右；而且为到达B，必须有n个向右走，m个向上走；如此，从这m+n个格子里选择n个向右走就ok了（剩下的就向上走，当然可以选择m向上走，剩下向右走）。答案为 $C_{n+m}^n$

---

给你一个字符串 s，找到 s 中最长的 回文子串 。

思路：$dp_{(i,j)}$ 表示字串（i，j）是否是回文，请自己设计状态转移方程和初始化方式

---

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。你可以对一个单词进行如下三种操作：插入一个字符、删除一个字符、替换一个字符

思路：对于两个字符串，看似一共有六种操作，但是去除等价的操作之后，本质不同的操作实际上只有三种：在单词 A 中插入一个字符；在单词 B 中插入一个字符；修改单词 A 的一个字符。

• 若 A 和 B 的最后一个字母相同：D[i][j]=min(D[i][j−1]+1,D[i−1][j]+1,D[i−1][j−1])=1+min(D[i][j−1],D[i−1][j],D[i−1][j−1]−1)

• 若 A 和 B 的最后一个字母不同：D[i][j]=1+min(D[i][j−1],D[i−1][j],D[i−1][j−1])

• 对于边界情况，一个空串和一个非空串的编辑距离为 D[i][0] = i 和 D[0][j] = j

---

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案

输入：n = 5
输出：[0,1,1,2,1,2]
解释：
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

思路：

• 如果 x 是偶数，则 bits[x]=bits[⌊x/2⌋]；

• 如果 x 是奇数，则 bits[x]=bits[⌊x/2⌋]+1。

即for(int i=0;i<=n;++i)dp[i]=dp[i>>1]+(i&1);