二、动态规划(dp)
知识点
思路：
化零为整：最值、个数。零散的->集合。
化整为零：集合化为各个子集。
常见模型：组合模型(背包问题)、路线模型(摘花生问题)、序列模型（最长子序列问题）
下面3题是最为常见的三种模型，是对应三道例题y总给出的思路：
下面例题1：
例题2：
例题3：
模板题
例题1：AcWing 2.01背包问题【模板题】
题目链接：2. 01背包问题
学习博客：AcWing 2. 01背包问题（状态转移方程讲解）
解法一：使用二维数组
分析：
定义：dp[i][j]，表示当前是截止到第i个背包，j表示第i个背包体积为j的最大价值数量。
递推方程：dp[i][j] = Math.max(dp[i - 1][j]， dp[i - 1][j - v[i]] + w[i])
dp初始化：默认从i=1，j=1开始。
对应题目给出的输入与输出： 输入： 4 5 1 2 2 4 3 4 4 5 输出： 8
复杂度分析：时间复杂度O(n2)；空间复杂度O(n2) ，本题最大为1000，那么1000x1000=100万，是可以接受的。
解法：
import java.util.*; import java.io.*; class Main { private static final int N = 1005; private static int n, V; private static int[] v = new int[N], w = new int[N]; private static int[][] dp = new int[N][N]; public static void main(String[] args)throws Exception { BufferedReader cin = new BufferedReader(new InputStreamReader(System.in)); String[] s = cin.readLine().split(" "); n = Integer.valueOf(s[0]); V = Integer.valueOf(s[1]); for (int i = 1; i <= n; i++) { s = cin.readLine().split(" "); v[i] = Integer.valueOf(s[0]); w[i] = Integer.valueOf(s[1]); } //两层for循环来去枚举出所有dp[i][j]对应背包体积的最大价值 for (int i = 1; i <= n; i++) { //j表示当前经过到第i个背包时，最大的包裹体积 for (int j = 1; j <= V; j++) { if (j >= v[i]) { //尝试去通过递推方程来求最优解 dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]); }else { dp[i][j] = dp[i - 1][j]; } } } System.out.printf("%d", dp[n][V]); } }
解法二：使用一维数组
分析：
在解法一种的二维数组我们可以得到一个规律就是我们在每次枚举一组数据时，都是基于上一次记录，也就是说在dp[i]层仅仅只与dp[i-1]层会相关，其他类似于i - 2、i - 3层都不会涉及。
此时递推方程为：dp[i] = Math.max(dp[i], dp[j - v] + w) (j >= v)，计算的过程性质与解法一实质上并没有区别。
复杂度分析：时间复杂度O(n2)；空间复杂度O(n) ，优化了空间效率
解题：
import java.util.*; import java.io.*; class Main { private static final int N = 1005; private static int n, V; //一维dp数组 private static int v, w; private static int[] dp = new int[N]; public static void main(String[] args)throws Exception { BufferedReader cin = new BufferedReader(new InputStreamReader(System.in)); String[] s = cin.readLine().split(" "); n = Integer.valueOf(s[0]); V = Integer.valueOf(s[1]); //两层for循环，记录仅仅使用一维数组 for (int i = 1; i <= n; i++) { s = cin.readLine().split(" "); v = Integer.valueOf(s[0]); w = Integer.valueOf(s[1]); for (int j = V; j >= v; j--) { //递推方程 dp[j] = Math.max(dp[j], dp[j - v] + w); } } System.out.printf("%d", dp[V]); } }
例题2：AcWing 1015. 摘花生【简单】
来源题目：《信息学奥赛一本通》
题目链接：1015. 摘花生
思路1：dp二维数组
分析：
定义dp：dp[i][j]表示在第i行第j列上可取得的最多花生。
确定dp公式：dp[i][j] = Math.max(dp[i - 1][j] + arr[i][j], dp[i][j - 1] + arr[i][j])
题解：
复杂度分析：时间复杂度O(n2)；空间复杂度O(n2)。最大N = 105，不会超时与超出内存空间。
//count //n m //arr import java.util.*; import java.io.*; class Main { static final int N = 105; static int count, n, m; static int[][] arr = new int[N][N]; //定义dp方程 static int[][] dp = new int[N][N]; public static void main(String[] args)throws Exception { BufferedReader cin = new BufferedReader(new InputStreamReader(System.in)); count = Integer.valueOf(cin.readLine()); while (count != 0) { String[] s = cin.readLine().split(" "); n = Integer.valueOf(s[0]); m = Integer.valueOf(s[1]); //初始化 for (int i = 1; i <= n; i++) { s = cin.readLine().split(" "); for (int j = 1; j <= m; j++) { arr[i][j] = Integer.valueOf(s[j - 1]); } } //dp：dp[i][j] = Math.max(dp[i - 1][j] + arr[i][j], dp[i][j - 1] + arr[i][j]); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { dp[i][j] = Math.max(dp[i - 1][j] + arr[i][j], dp[i][j - 1] + arr[i][j]); } } System.out.printf("%d\n", dp[n][m]); count--; } } }
思路2：dp一维数组
分析：
由于上面dp二维数组每一行仅仅只与上一行有关，所以我们这里可以将其优化为一维数组，推举过程如下：
dp公式为：dp[j] = Math.max(dp[j - 1] + arr[i][j], dp[j] + arr[i][j])
题解：
复杂度分析：时间复杂度O(n2)；空间复杂度O(n)。最大N = 105，不会超时与超出内存空间。
//count //n m //arr import java.util.*; import java.io.*; class Main { static final int N = 105; static int count, n, m; static int[][] arr = new int[N][N]; //定义dp方程 static int[] dp; public static void main(String[] args)throws Exception { BufferedReader cin = new BufferedReader(new InputStreamReader(System.in)); count = Integer.valueOf(cin.readLine()); while (count != 0) { String[] s = cin.readLine().split(" "); n = Integer.valueOf(s[0]); m = Integer.valueOf(s[1]); //初始化 for (int i = 1; i <= n; i++) { s = cin.readLine().split(" "); for (int j = 1; j <= m; j++) { arr[i][j] = Integer.valueOf(s[j - 1]); } } //重新开辟数组（防止上一组的错误数据） dp = new int[N]; //dp：dp[j] = Math.max(dp[j - 1] + arr[i][j], dp[j] + arr[i][j]); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { dp[j] = Math.max(dp[j - 1] + arr[i][j], dp[j] + arr[i][j]); } } System.out.printf("%d\n", dp[m]); count--; } } }
例题3：AcWing. 4557. 最长上升子序列【简单】
来源：POJ2533 , kuangbin专题
题目链接：4557. 最长上升子序列
学习博客：最长上升子序列（c++图文详解）
分析：
定义：dp[i]，在1-i中有最大长度数量。
转移方程：dp[i] = dp[j] + 1
题解：
复杂度分析：时间复杂度O(n2)；空间复杂度O(n)。本题最大为1005，时间上不会超过范围。
//定义：dp[i]表示当前在i位置的最长子序列的长度 //状态转移方程：dp[i] = dp[j] + 1 (arr[i] > arr[j] && dp[j] >= dp[i]) 最长：res = Math.max(dp[i], res) import java.util.*; import java.io.*; class Main { static final int N = 1005; static int n; static int arr[] = new int[N]; //定义dp数组 static int dp[] = new int[N]; static int res = 1; public static void main(String[] args)throws Exception { BufferedReader cin = new BufferedReader(new InputStreamReader(System.in)); n = Integer.valueOf(cin.readLine()); String[] s = cin.readLine().split(" "); for (int i = 0; i < n; i++) { arr[i] = Integer.valueOf(s[i]); } //初始化dp数组每位都是1（因为自己本身就是1个） Arrays.fill(dp, 1); //进行递推 for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { //若是后面的元素比之前的大，那么直接拿取之前计算的dp长度值+1 && 之前的元素连续数量>=当前元素的数量（无该条件，就可能会被原本小于本身的覆盖掉） if (arr[i] > arr[j] && dp[j] >= dp[i]) { //转移方程 dp[i] = dp[j] + 1; //求取最大值 res = Math.max(res, dp[i]); } } } System.out.printf("%d", res); } }
习题
习题1：Acwing 1212. 地宫取宝【中等，蓝桥杯】
分析：
题目类型：摘花生与最长上升子序列的结合版，摘花生扩展版。
三个细节：
从左到右。
每次取宝贝是递增。
到终点取出k件方案数。
根据给出的题分析相应的时间复杂度：f(i, j, k, c)，50x50x12x13x(25)：四层循环+一个循环。
上y总的分析图：
dp定义f[i,j,k,c]：表示从起点走到(i,j)位置，已经取了k间物品，最后一件物品的价值是C的合法方案。
k指的是题目要求的k件。
c指的是题目要求的物品价值。
状态方程：
不取的情况：dp[i][j][k][c] = dp[i - 1][j][k][c] + dp[i][j - 1][k][c]
取的情况：dp[i][j][k][c] = dp[i - 1][j][k][c] + dp[i][j - 1][k][c] （u > 0 && c == w[i][j]，c’ ∈ (1, v)）
初始化：
f(1, 1, 1, w(1, 1)) = 1 表示取
f(1, 1, 0, -1)=1 表示不取
第四个位置为-1表示的是没有取。由于在数组中无法使用-1表示，所以全部会进行+1，也就是原本是-1 - 12，现在是0 - 13，0表示的就是没有取。【注意：因为这个原因，所以我们需要在给初始的w[i][j]+1】
题解：
复杂度分析：时间复杂度O(n.m.k.c)；空间复杂度O(n.m.k.c)，不超时，满足题目
// 2 2 2 // 1 2 // 2 1 //n = 2 m = 2 k = 2 //arr[n][m] import java.util.*; import java.io.*; class Main { static final int N = 52, MOD = 1000000007;//int型是23亿，一个MOD就是10亿，最多只能连续两个相加 static int n, m, k; static int[][] w = new int[N][N]; //定义dp数组 static int[][][][] dp = new int[N][N][13][14];//dp(i, j, k, c) public static void main(String[] args)throws Exception { BufferedReader cin = new BufferedReader(new InputStreamReader(System.in)); String[] s = cin.readLine().split(" "); n = Integer.valueOf(s[0]); m = Integer.valueOf(s[1]); k = Integer.valueOf(s[2]); for (int i = 1; i <= n; i++) { s = cin.readLine().split(" "); for (int j = 1; j <= m; j++) { //0表示当前没有取且取得的价值为-1（数组中无法使用-1来表示下标） w[i][j] = Integer.valueOf(s[j - 1]) + 1; } } //初始化：左上角第一个格子取 or 不取 dp[1][1][1][w[1][1]] = 1; //在第一个格子上 dp[1][1][0][0] = 1; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (i == 1 && j == 1) continue; for (int u = 0; u <= k; u++) { //u表示k，表示在(i,j)取了u件物品 for (int v = 0; v <= 13; v++) { //v表示c，表示在(i,j)取了u件物品的价值 //不取（直接加上上、左的方案） int val = dp[i][j][u][v]; val = (val + dp[i - 1][j][u][v]) % MOD; val = (val + dp[i][j - 1][u][v]) % MOD; dp[i][j][u][v] = val; //取 //对于取了0件，但是最后价值是非0的我们要省略掉 if(u > 0 && v == w[i][j]) { //这个就是最长子序列模型 for (int c = 0; c < v; c++) { val = (val + dp[i - 1][j][u - 1][c]) % MOD; val = (val + dp[i][j - 1][u - 1][c]) % MOD; dp[i][j][u][v] = val; } } } } } } //统计所有的方案数 int res = 0; for (int i = 0; i <= 13; i++) res = (res + dp[n][m][k][i]) % MOD; System.out.printf("%d", res); } }
习题2：AcWing 1214.波动数列【中等，蓝桥杯】
题目链接：1214. 波动数列
题目类型：
背包问题的变形，组合模型
背包问题的简单变种或者组合问题的变种
首先根据题目确定求解的问题：长度为 n 和为 s 而且后一项总是比前一项增加 a 或者减少 b 的整数数列可能有多少种呢？
实际上是一个组合问题，拆分一下就是说求得最后长度为n，和为s的方案(后一项比前一项增加a的方案 + 后一项比前一项增加b的方案)种数。
题目给出了数据范围：1≤n≤1000，那么大概就是n2的时间复杂度，那么基本就是两层循环。
给出y总的分析图：
转移方程的推演：f[i][j] = f[i - 1][(j - ai) % n] + f[i - 1][(j + bi) % n] ，过程如下：
设定数列的初始值为x，后一个数比前一个数增加或减少称之为d ∈ (+a, -b)，此时就可以列出公式：
s = x + (x + d1) + (x + d1 + d2) + (x + d1 + d2 + d3) + … + (x + d1 + … + dn-1)，拆分下为：
x.n + (n - 1).d1 + (n - 2).d2 + (n - 3)d3 + 1.dn-1 = s，将x.n右边的移动到s的式子上即为：
x.n = s - {(n - 1).d1 + (n - 2).d2 + (n - 3)d3 + 1.dn-1 }，此时可以化成一个除法公式为：
x =
s − [ ( n − 1 ) . d 1 + ( n − 2 ) . d 2 + ( n − 3 ) d 3 + 1. d n − 1 ] n {s - [(n - 1).d1 + (n - 2).d2 + (n - 3)d3 + 1.d~n-1~] \over n}
n
s−[(n−1).d1+(n−2).d2+(n−3)d3+1.d n−1 ]
，
此时我们来举一个例子，1 =
6 − 2 4 6 - 2 \over 4
4
6−2
，实际上对于后面的2可以使用6 % 4来表示，那么对于上方x的等式，我们可以也依据次来进行表示
s % n = [(n - 1).d1 + (n - 2).d2 + (n - 3)d3 + 1.dn-1]
此时若是有i个数，那么后一个数相对于前一个数相加相减的序列为：d1, d2, d3, … di (设+a)
若是想要计算截至当前第i个元素其和，式子为前i - 1个累加的和+当前第i个和 = s % n，也就是上面的s % n = [(n - 1).d1 + (n - 2).d2 + (n - 3)d3 + 1.dn-1]
我们用c变量来表示前i - 1个累加的和，最后一项则是上面图片里的a.i 或者-b.i即可，那么就是c + ai = s % n 或者 c - bi = s % n
如何拿到前i - 1累加的和呢？实际上前i - 1个累加的和就是c，那么只需要借助上面的公式c = (s - ai) % n 或者 c = (s + bi) % n即可得到了，那么递推公式为：f[i][s] = f[i - 1][(s - ai) % n] + f[i - 1][(s + bi) % n]
在实际代码中是用j去表示s，那么公式就是：f[i][j] = f[i - 1][(j - ai) % n] + f[i - 1][(j + bi) % n]
初始化：f[0][0] = 1，1个数都不取的话，余数只能为0，所以设置初始位置为1。
题解
复杂度分析：时间复杂度O(n2)；空间复杂度O(n2)
import java.util.*; import java.io.*; class Main { static final int N = 1010, MOD = 100000007; static int n, s, a, b; static int[][] dp = new int[N][N]; //防止a % b出现负数的情况，a % b 最小值为-b + 1，此时加上b就是>0，最后放置超过b所以再%一次 public static int getMod(int a, int b) { return (a % b + b) % b; } public static void main(String[] args) { Scanner cin = new Scanner(System.in); n = cin.nextInt(); s = cin.nextInt(); a = cin.nextInt(); b = cin.nextInt(); //初始化 dp[0][0] = 1; for (int i = 1; i < n; i++) { for (int j = 0; j < n; j++) { //转移方程 dp[i][j] = (dp[i - 1][getMod(j - a * i, n)] + dp[i - 1][getMod(j + b * i, n)]) % MOD; } } //防止s % n出现负数，此时就需要调用getMod函数 System.out.printf("%d", dp[n - 1][getMod(s, n)]); } }
