动态规划总结
题型总结
- 线性DP
- 区间DP
- 树形DP
-
注意事项
一般方案数，或者最大最小的最优化问题，需要使用动态规划进行求解。
- 注意遍历的方向，从前往后遍历，还是从右下角往左上角遍历。不同遍历方式带来的影响不一样。
- 有可能动态规划之前需要对数组进行处理，比如求前缀和等。
- 状态定义不一定表示最终的结果，可能最终结果还需要遍历一遍DP数组求最大值或者最小值。
- 对于不好处理的数据，可以在数据前补一个0；让数组从位置1开始遍历，注意结束地方是小于等于。
- 状态转移方式：
- 1.用其所依赖的状态来更新当前状态（80%）
- 2.用当前状态来更新依赖他的状态（20%）
例题
线性DP
1. 分割数组的最大值
描述
方法一、动态规划
思路
「将数组分割为 mm 段，求……」是动态规划题目常见的问法。
本题中，我们可以令 f[i][j] 表示将数组的前 i 个数分割为 j 段所能得到的最大连续子数组和的最小值。在进行状态转移时，我们可以考虑第 j 段的具体范围，即我们可以枚举 k，其中前 k 个数被分割为 j−1 段，而第 k+1 到第 i 个数为第 j 段。此时，这 j 段子数组中和的最大值，就等于 f[k][j−1] 与 sub(k+1,i) 中的较大值，其中 sub(i,j) 表示数组 nums 中下标落在区间 [i,j] 内的数的和。
由于我们要使得子数组中和的最大值最小，因此可以列出如下的状态转移方程：
对于状态 f[i][j]，由于我们不能分出空的子数组，因此合法的状态必须有 i≥j。对于不合法（i<j）的状态，由于我们的目标是求出最小值，因此可以将这些状态全部初始化为一个很大的数。在上述的状态转移方程中，一旦我们尝试从不合法的状态 f[k][j−1] 进行转移，那么 max(⋯) 将会是一个很大的数，就不会对最外层的 min{⋯} 产生任何影响。
此外，我们还需要将 f[0][0] 的值初始化为 0。在上述的状态转移方程中，当 j=1 时，唯一的可能性就是前 i 个数被分成了一段。如果枚举的 k=0，那么就代表着这种情况；如果 k =0，对应的状态 f[k][0] 是一个不合法的状态，无法进行转移。因此我们需要令 f[0][0] = 0。
代码
class Solution {public int splitArray(int[] nums, int m) {int n = nums.length;int[][] f = new int[n + 1][m + 1];for (int i = 0; i <= n; i++) {Arrays.fill(f[i], Integer.MAX_VALUE);}int[] sub = new int[n + 1];for (int i = 0; i < n; i++) {sub[i + 1] = sub[i] + nums[i];}f[0][0] = 0;for (int i = 1; i <= n; i++) {for (int j = 1; j <= Math.min(i, m); j++) {for (int k = 0; k < i; k++) {f[i][j] = Math.min(f[i][j], Math.max(f[k][j - 1], sub[i] - sub[k]));}}}return f[n][m];}}
class Solution:
def splitArray(self, nums: List[int], m: int) -> int:
n = len(nums)
dp = [[10**18] * (m + 1) for _ in range(n + 1)]
sub = [0]
for num in nums:
sub.append(sub[-1] + num)
dp[0][0] = 0
for i in range(1, n + 1):
for j in range(1, min(i, m) + 1):
for k in range(i):
dp[i][j] = min(dp[i][j], max(dp[k][j-1], sub[i] - sub[k]))
return dp[n][m]
复杂度分析
- 时间复杂度：O(n^2 m)，其中 n 是数组的长度，m 是分成的非空的连续子数组的个数。总状态数为 O(n×m)，状态转移时间复杂度 O(n)，所以总时间复杂度为 O(n^2 m)。
- 空间复杂度：O(n×m)，为动态规划数组的开销。
方法二、二分查找+贪心
思路及算法
「使……最大值尽可能小」是二分搜索题目常见的问法。
本题中，我们注意到：当我们选定一个值 x，我们可以线性地验证是否存在一种分割方案，满足其最大分割子数组和不超过 x。策略如下：
贪心地模拟分割的过程，从前到后遍历数组，用 sum 表示当前分割子数组的和，cnt 表示已经分割出的子数组的数量（包括当前子数组），那么每当 sum 加上当前值超过了 x，我们就把当前取的值作为新的一段分割子数组的开头，并将 cnt 加 1。遍历结束后验证是否 cnt 不超过 m。
这样我们可以用二分查找来解决。二分的上界为数组 nums 中所有元素的和，下界为数组 nums 中所有元素的最大值。通过二分查找，我们可以得到最小的最大分割子数组和，这样就可以得到最终的答案了。
代码
class Solution:
def splitArray(self, nums: List[int], m: int) -> int:
def check(x: int) -> bool:
total, cnt = 0, 1
for num in nums:
if total + num > x:
cnt += 1
total = num
else:
total += num
return cnt <= m
left = max(nums)
right = sum(nums)
while left < right:
mid = (left + right) // 2
if check(mid):
right = mid
else:
left = mid + 1
return left
class Solution {
public int splitArray(int[] nums, int m) {
int left = 0, right = 0;
for (int i = 0; i < nums.length; i++) {
right += nums[i];
if (left < nums[i]) {
left = nums[i];
}
}
while (left < right) {
int mid = left + (right - left) / 2;
if (check(nums, mid, m)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
public boolean check(int[] nums, int x, int m) {
int sum = 0, cnt = 1;
for (int num : nums) {
if (sum + num > x) {
cnt += 1;
sum = num;
} else {
sum += num;
}
}
return cnt <= m;
}
}
复杂度分析
- 时间复杂度：O(n×log(sum−maxn))，其中 sum 表示数组 nums 中所有元素的和，maxn 表示数组所有元素的最大值。每次二分查找时，需要对数组进行一次遍历，时间复杂度为 O(n)，因此总时间复杂度是 O(n×log(sum−maxn))。
- 空间复杂度：O(1)。
2. 01背包
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0
输出样例：4 5 1 2 2 4 3 4 4 5
思路8
状态转移方程：
定义f[i][j]:前i个物品，背包容量j下的最优解
1）当前背包容量不够（j < w[i]），为前i-1个物品最优解：f[i][j] = f[i-1][j]
2）当前背包容量够，判断选与不选第i个物品
选：f[i][j] = f[i-1][j-w[i]] + v[i]
不选：f[i][j] = f[i-1][j]
c++代码： ```cppinclude
using namespace std;
const int MAXN = 1005; int w[MAXN]; // 重量 int v[MAXN]; // 价值 int f[MAXN][MAXN]; // f[i][j], j重量下前i个物品的最大价值
int main()
{
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; ++i)
cin >> w[i] >> v[i];
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
{
// 当前重量装不进，价值等于前i-1个物品
if(j < w[i])
f[i][j] = f[i-1][j];
// 能装，需判断
else
f[i][j] = max(f[i-1][j], f[i-1][j-w[i]] + v[i]);
}
cout << f[n][m];
return 0;
}
**优化**<br />(动规+一维数组)<br />状态转移方程为：f[j] = max(f[j], f[j-w[i]] + v[i]<br />C++ 代码
```cpp
for(int i = 1; i <= n; ++i)
{
for(int j = m; j >= 0; --j)
if(j >= w[i])
f[j] = max(f[j], f[j-w[i]] + v[i]);
}
注意枚举j必须从m开始
Python代码：
n, m = map(int, input().split())
v, w = [0], [0]
for i in range(n):
line = list(map(int, input().split()))
v.append(line[0])
w.append(line[1])
dp = [[0] * (m + 1) for _ in range(n+1)]
for i in range(1, n+1):
for j in range(0, m+1):
dp[i][j] = dp[i-1][j]
if j >= v[i]:
dp[i][j] = max(dp[i][j], dp[i-1][j- v[i]] + w[i])
print(dp[n][m])
Java代码：
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int[] v = new int[1010];
int[] w = new int[1010];
for (int i = 1; i <= n; i++) {
v[i] = in.nextInt();
w[i] = in.nextInt();
}
int[][] dp = new int[n+1][m+1];
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
dp[i][j] = dp[i-1][j];
if (j >= v[i]) {
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - v[i]] + w[i]);
}
}
}
System.out.println(dp[n][m]);
}
}
Python 一维dP：
n, m = map(int, input().split())
v, w = [0], [0]
for i in range(n):
line = list(map(int, input().split()))
v.append(line[0])
w.append(line[1])
dp = [0] * (m + 1)
for i in range(1, n+1):
for j in range(m, v[i]-1, -1):
dp[j] = max(dp[j], dp[j- v[i]] + w[i])
print(dp[m])
Java 一维dp：
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int[] v = new int[1010];
int[] w = new int[1010];
for (int i = 1; i <= n; i++) {
v[i] = in.nextInt();
w[i] = in.nextInt();
}
int[] dp = new int[m+1];
for (int i = 1; i <= n; i++) {
for (int j = m; j >= v[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
}
}
System.out.println(dp[m]);
}
}
3. 完全背包
有 N 种物品和一个容量是 VV的背包，每种物品都有无限件可用。
第 i 种物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 种物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0
4 5
1 2
2 4
3 4
4 5
输出样例：
10
思路 
代码
Python代码：
if __name__ == '__main__':
n, m = map(int, input().split())
dp = [0] * (m + 1)
for i in range(1, n + 1):
v, w = map(int, input().split())
for j in range(v, m + 1):
dp[j] = max(dp[j], dp[j - v] + w)
print(dp[m])
Java代码：
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int[] v = new int[1010];
int[] w = new int[1010];
for (int i = 1; i <= n; i++) {
v[i] = in.nextInt();
w[i] = in.nextInt();
}
int[] dp = new int[m+1];
for (int i = 1; i <= n; i++) {
for (int j = v[i]; j <= m; j++) {
dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
}
}
System.out.println(dp[m]);
}
}
4. AcWing 272. 最长公共上升子序列
描述
第一行包含一个整数N，表示数列A，B的长度。
第二行包含N个整数，表示数列A。
第三行包含N个整数，表示数列B。
输出格式
输出一个整数，表示最长公共上升子序列的长度。
数据范围
1≤N≤3000,序列中的数字均不超过2^31−1
输入样例：
4
2 2 1 3
2 1 2 3
输出样例：
2
思路
- 动态规划
- 状态定义，f[i][j]表示，所有在A[1..i]和B[1…j]中都出现过，且以B[j]结尾的公共上升子序列集合的最大值。
- 状态转移
- A[i]不包含在公共子序列中，f[i][j] = f[i-1][j]
- A[i]在公共子序列中，那么必须有A[i] == B[j]，遍历B[1…j-1] 如果小于B[j]，记录一个最大值maxv，那么最终f[i][j] = max(f[i][j], maxv)
Python代码：O(n）
n = int(input())
a = [0] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))
f = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(1, n+1):
for j in range(1, n+1):
f[i][j] = f[i-1][j]
if a[i] == b[j]:
maxv = 1
for k in range(1, j):
if b[k] < b[j]:
maxv = max(maxv, f[i-1][k] + 1)
f[i][j] = max(f[i][j], maxv)
ans = 0
for i in range(n+1):
ans = max(ans, f[n][i])
print(ans)
Java代码：O(n）
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int[] a = new int[3010];
int[] b = new int[3010];
int[][] f = new int[3010][3010];
int n = in.nextInt();
for (int i = 1; i <= n; i++) {
a[i] = in.nextInt();
}
for (int i = 1; i <= n; i++) {
b[i] = in.nextInt();
}
for(int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
f[i][j] = f[i-1][j];
int maxv = 1;
if (a[i] == b[j]) {
for (int k = 1; k < j; k++) {
if (b[k] < b[j]) {
maxv = Math.max(maxv, f[i-1][k] + 1);
}
}
f[i][j] = Math.max(f[i][j], maxv);
}
}
}
int ans = 0;
for (int i = 1; i <=n; i++) {
ans = Math.max(ans, f[n][i]);
}
System.out.println(ans);
}
}
Python代码：O(n)
n = int(input())
a = [0] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))
f = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(1, n+1):
maxv = 1
for j in range(1, n+1):
f[i][j] = f[i-1][j]
if a[i] == b[j]:
f[i][j] = max(maxv, f[i][j])
if b[j] < a[i]:
maxv = max(maxv, f[i-1][j] + 1)
ans = 0
for i in range(n+1):
ans = max(ans, f[n][i])
print(ans)
5.最长重复子数组
思路
- 状态定义：f[i][j]表示以位置A[i]，A[j]为开始位置的公共子数组的长度。
状态转移，从后向前遍历，如果A[i] == B[j] ，那么就等于后一个为位置的公共子数组的长度 + 1。
if a[i] == b[j] then f[i][j] = f[i+1][j+1] + 1 else f[i][j] = 0Python代码：
class Solution: def findLength(self, a: List[int], b: List[int]) -> int: m = len(a) n = len(b) f = [[0] * (n + 1) for _ in range(m + 1)] ans = 0 for i in range(m-1, -1, -1): for j in range(n-1, -1, -1): if a[i] == b[j]: f[i][j] = f[i+1][j+1] + 1 else: f[i][j] = 0 ans = max(ans, f[i][j]) return ansJava代码：
class Solution { public int findLength(int[] a, int[] b) { int m = a.length; int n = b.length; int[][] f = new int[m+1][n+1]; int ans = 0; for (int i = m-1; i >= 0; i--) { for (int j = n -1; j >= 0; j--) { if (a[i] == b[j]) { f[i][j] = f[i+1][j+1] + 1; } else { f[i][j] = 0; } ans = Math.max(ans, f[i][j]); } } return ans; } }6. AcWing 271. 杨老师的照相排列
每组数据两行，第一行包含一个整数k表示总排数。
第二行包含k个整数，表示从后向前每排的具体人数。
当输入k=0的数据时，表示输入终止，且该数据无需处理。
输出格式
每组测试数据输出一个答案，表示不同安排的数量。
每个答案占一行。
数据范围
1≤k≤5,学生总人数不超过30人。
输入样例：1 30 5 1 1 1 1 1 3 3 2 1 4 5 3 3 1 5 6 5 4 3 2 2 15 15 0输出样例：
1 1 16 4158 141892608 9694845思路
状态定义：f[a,b,c,d,e]表示所有第一排a个人，第二排有b个人，第三排….第五排有e个人的方案。
- 状态转移：将最后一个人放在第一排，或者第二排，或者第三排的….。
- f[a, b, c, d, e] = f[a-1, b, c, d, e] + f[a, b-1, c, d, e] + …..
- 当a,b,c,d,e中有一个为0时，就返回0；还需要满足，第一排的人数大于等于第二排的人数，依次类推。
代码
Java代码：
import java.util.*;
public class Main{
void run(){
while(jin.hasNext()){
int k = jin.nextInt();
if (k == 0) break;
Arrays.fill(row, 0);
for (int i = 0 ; i < k ; i++) row[i] = jin.nextInt();
for (int a = 0; a <= row[0] ; a++){
for (int b = 0 ; b <= row[1]; b++){
for (int c = 0; c <= row[2] ; c++){
for (int d = 0; d <= row[3]; d ++){
for (int e = 0; e <= row[4]; e++){
f[a][b][c][d][e] = 0;
}
}
}
}
}
f[0][0][0][0][0] = 1;
for (int a = 0; a <= row[0] ; a++){ // a<= row[0] 最大可以有row[0] 个人
for (int b = 0 ; b <= Math.min(a, row[1]); b++){
for (int c = 0; c <= Math.min(b, row[2]) ; c++){
for (int d = 0; d <= Math.min(c, row[3]); d ++){
for (int e = 0; e <= Math.min(d, row[4]); e++)
{
long v = 0;
if (a > 0 && a - 1 >= b) v += f[a-1][b][c][d][e]; // a-1 >= b a去掉最后一个人时可能和b相等
if (b > 0 && b - 1 >= c) v += f[a][b-1][c][d][e];
if (c > 0 && c - 1 >= d) v += f[a][b][c-1][d][e];
if (d > 0 && d - 1 >= e) v += f[a][b][c][d-1][e];
if (e > 0) v += f[a][b][c][d][e-1];
f[a][b][c][d][e] += v;
}
}
}
}
}
System.out.println(f[row[0]][row[1]][row[2]][row[3]][row[4]]);
}
}
int maxR = 5;
int maxP = 31;
int[] row = new int[maxR];
long[][][][][] f = new long[maxP][maxP][maxP][maxP][maxP];
Scanner jin = new Scanner(System.in);
public static void main(String[] args) throws Exception {new Main().run();}
}
7. AcWing 274. 移动服务
一个公司有三个移动服务员，最初分别在位置1，2，3处。
如果某个位置（用一个整数表示）有一个请求，那么公司必须指派某名员工赶到那个地方去。
某一时刻只有一个员工能移动，且不允许在同样的位置出现两个员工。
从 p 到 q 移动一个员工，需要花费 c(p,q)。
这个函数不一定对称，但保证 c(p,p)=0。
给出N个请求，请求发生的位置分别为 p1p1~pNpN。
公司必须按顺序依次满足所有请求，且过程中不能去其他额外的位置，目标是最小化公司花费，请你帮忙计算这个最小花费。
输入格式
第1行有两个整数L,N，其中L是位置数量，N是请求数量，每个位置从1到L编号。
第2至L+1行每行包含L个非负整数，第i+1行的第j个数表示c(i,j) ，并且它小于2000。
最后一行包含N个整数，是请求列表。
一开始三个服务员分别在位置1，2，3。
输出格式
输出一个整数M，表示最小花费。
数据范围
3≤L≤2003≤L≤200,
1≤N≤10001≤N≤1000
输入样例：
5 9
0 1 1 1 1
1 0 2 3 2
1 1 0 4 1
2 1 5 0 1
4 2 3 4 0
4 2 4 1 5 4 3 2 1
输出样例：
5
思路
状态表示：f[i, x, y]，所有已经处理完前i个请求，且另外两个服务员在x, y两地的所有安排方案集合
8. 方格取数
思路状态定义：f[k,i1,i2]，表示所有从（1,1）走到（i1, k-i1）和（i2, k-i2）的所有路径的最大值
状态情况：
- 分类讨论，下下，右下，下右，右右，以下下为例 f[k,i1,i2] = f[k-1, i1-1,i2] + f[k-1,i1,i2-1] + t
当i1 == i2时，两点重合，t = w[i1][j1]，不重合时 t = w[i1][j1] + w[i2][j2]
区间DP
1. 石子合并
设有N堆石子排成一排，其编号为1，2，3，…，N。
每堆石子有一定的质量，可以用一个整数来描述，现在要将这N堆石子合并成为一堆。
每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。
例如有4堆石子分别为 1 3 5 2， 我们可以先合并1、2堆，代价为4，得到4 5 2， 又合并 1，2堆，代价为9，得到9 2 ，再合并得到11，总代价为4+9+11=24；
如果第二步是先合并2，3堆，则代价为7，得到4 7，最后一次合并代价为11，总代价为4+7+11=22。
问题是：找出一种合理的方法，使总的代价最小，输出最小代价。
输入格式
第一行一个数N表示石子的堆数N。
第二行N个数，表示每堆石子的质量(均不超过1000)。
输出格式
输出一个整数，表示最小代价。
数据范围
1≤N≤300
输入样例：4 1 3 5 2输出样例：
22思路
代码
Python代码： ```python def min_cost(n, arr): s = [0] for num in arr: s.append(s[-1] + num)f = [[0] * (n + 1) for _ in range(n + 1)] for m_len in range(2, n+1): for i in range(1, n-m_len+2):
j = i + m_len - 1 f[i][j] = float('inf') for k in range(i, j): f[i][j] = min(f[i][j], f[i][k] + f[k+1][j] + s[j] - s[i-1])return f[1][n]
if name == ‘main‘: n = int(input()) arr = list(map(int, input().split())) print(min_cost(n, arr))
Java代码：
```java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] s = new int[n+1];
for (int i = 1; i <= n; i++) {
s[i] = in.nextInt();
}
int[] preSum = new int[n+1];
for (int i = 1; i <= n; i++) {
preSum[i] = preSum[i-1] + s[i];
}
int[][] dp = new int[n+1][n+1];
for (int len = 2; len <= n; len++) {
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
dp[i][j] = Integer.MAX_VALUE;
for (int k = i; k < i + len - 1; k++) {
dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j] + preSum[j] - preSum[i-1]);
}
}
}
System.out.println(dp[1][n]);
}
}
2. 猜数字大小II
思路
- 二分肯定不行，比如 1 2 3 4 5，二分需要7块钱， 如果先猜4只需要6块钱。
- 动态规划
- 以 i 为第一次尝试找到最小开销的过程可以被分解为找左右区间内最小开销的子问题。对于每个区间，我们重复问题拆分的过程，得到更多子问题，这启发我们可以用 DP 解决这个问题。
- 其中 dp(i, j)代表在 (i, j)中最坏情况下最小开销的代价。现在我们只需要考虑如何求出这个 dp 数组。如果区间只剩下一个数 k ，那么猜中的代价永远为 0 ，因为我们区间里只剩下一个数字，也就是说，所有的 dp(k, k)都初始化为 0 。然后，对于长度为 2 的区间，我们需要所有长度为 1 的区间的结果。由此我们可以看出，为了求出长度为 len 区间的解，我们需要所有长度为len−1 的解。因此我们按照区间长度从短到长求出 dp 数组。
- 现在，我们应该按照什么办法来求出 dp 矩阵呢？对于每个 dp(i, j) ，当前长度为 len=j−i+1 。我们遵照方法 1 中办法，依次挑选每个数字作为第一次尝试的答案，可以求出最小开销：
但是在计算开销的时候我们有一个便利之处，就是我们已经知道了小于 len 长度 dp 数组的所有答案。因 此 dp方程式变成了：
代码
Java代码：
class Solution {
public int getMoneyAmount(int n) {
int[][] dp = new int[n+1][n+1];
int ans = Integer.MAX_VALUE;
for (int len = 2; len <= n; len++) {
for (int start = 1; start + len - 1 <= n; start++) {
int curMin = Integer.MAX_VALUE;
for (int k = start; k < start + len - 1; k++) {
dp[start][start + len - 1] = k + Math.max(dp[start][k-1], dp[k+1][start + len - 1]);
curMin = Math.min(curMin, dp[start][start + len - 1]);
}
dp[start][start + len - 1] = curMin;
}
}
return dp[1][n];
}
}
Python代码：
class Solution:
def getMoneyAmount(self, n: int) -> int:
dp = [[0] * (n + 1) for _ in range(n + 1)]
for lens in range(2, n+1):
for start in range(1, n - lens + 2):
cur_min = float('inf')
for k in range(start, start + lens - 1):
cur_min = min(cur_min, k + max(dp[start][k-1], dp[k+1][start + lens - 1]))
dp[start][start + lens - 1] = cur_min
return dp[1][n]
3. 戳气球
思路
- 回溯，枚举每一次选择的位置
- 递归
- 动态规划
代码
回溯法-Java-超时:
class Solution {
public static int ans = 0;
public int maxCoins(int[] nums) {
List<Integer> numsList = new ArrayList<>();
for (int num : nums) {
numsList.add(num);
}
helper(numsList, 0);
return ans;
}
public void helper(List<Integer> nums, int coins) {
// bundary
if (nums.size() == 0) {
ans = Math.max(ans, coins);
}
// search
for (int i = 0; i < nums.size(); i++) {
int temp = nums.get(i);
int delta = temp * (i - 1 < 0? 1: nums.get(i-1)) * (i + 1 > nums.size() - 1 ? 1 : nums.get(i+1));
nums.remove(i);
helper(nums, coins + delta);
nums.add(i, temp);
}
}
}
递归-Java：
class Solution {
public static int ans = 0;
public static int[][] dp;
public int maxCoins(int[] nums) {
int n = nums.length;
List<Integer> numsList = new ArrayList<>();
for (int num : nums) {
numsList.add(num);
}
numsList.add(0, 1);
numsList.add(1);
dp = new int[n+2][n+2];
helper(numsList, 1, n);
return dp[1][n];
}
public int helper(List<Integer> numsList, int i, int j) {
// boundary
if (i > j) return 0;
if (dp[i][j] > 0) return dp[i][j];
// search
for (int k = i; k <= j; k++) {
int left = helper(numsList, i, k - 1);
int right = helper(numsList, k + 1, j);
int delta = numsList.get(k) * numsList.get(i-1) * numsList.get(j + 1);
dp[i][j] = Math.max(dp[i][j], left + right + delta);
}
return dp[i][j];
}
}
动态规划-自底向上方法-Java代码：
class Solution {
public int maxCoins(int[] nums) {
int n = nums.length;
int[] newNums = new int[n+2];
for (int i = 1; i <= nums.length; i++) {
newNums[i] = nums[i-1];
}
// 两边增加一个 1
newNums[0] = 1;
newNums[newNums.length - 1] = 1;
int[][] dp = new int[n+2][n+2];
// 区间长度 1 -> n
for (int len = 1; len <= n; len++) {
// 区间左端点 1
for (int i = 1; i + len - 1 <= n; i++) {
// 区间右端点
int j = i + len - 1;
for (int k = i; k <= j; k++) {
// 记录最大值
dp[i][j] = Math.max(dp[i][j], dp[i][k-1] + dp[k+1][j] + newNums[k] * newNums[i-1] * newNums[j+1]);
}
}
}
return dp[1][n];
}
}
计数DP
1.划分数
思路
- 动态规划：dp[i][j]表示j的i划分
- 状态转移：分两种情况，所有的划分都大于0，或者存在为0的划分
- dp[i][j] = dp[i][j-i] + dp[i-1][j]
代码
int n, m;
int dp[Max_M+1][Max_N+1]
void solve()
{
dp[0][0] = 1;
for (int i = 1; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (j - i >= 0) {
dp[i][j] = dp[i][j-i] + dp[i-1][j];
} else {
dp[i][j] = dp[i-1][j];
}
}
}
printf("%d\n", dp[m][n]);
}
环形DP
1. AcWing 414. 数字游戏
丁丁最近沉迷于一个数字游戏之中。
这个游戏看似简单，但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。
游戏是这样的，在你面前有一圈整数（一共n个），你要按顺序将其分为m个部分，各部分内的数字相加，相加所得的m个结果对10取模后再相乘，最终得到一个数k。
游戏的要求是使你所得的k最大或者最小。
例如，对于下面这圈数字（n=4，m=2）：
当要求最小值时，((2-1) mod 10)×((4+3) mod 10)=1×7=7，要求最大值时，为((2+4+3) mod 10)×(-1 mod 10)=9×9=81。
特别值得注意的是，无论是负数还是正数，对10取模的结果均为非负值。
丁丁请你编写程序帮他赢得这个游戏。
输入格式
输入文件第一行有两个整数，n和m。
以下n行每行一个整数，其绝对值不大于10000，按顺序给出圈中的数字，首尾相接。
输出格式
输出文件有两行，各包含一个非负整数。
第一行是你程序得到的最小值，第二行是最大值。
数据范围
1≤n≤50,
1≤m≤9
输入样例：
4 2
4
3
-1
2
输出样例：
7
81
思路
- 动态规划、区间和-前缀和
- 状态定义：F[L，R, K]表示从L 到 R 分成 K 组的最小值
- 枚举区间右端点，L + K - 2 —-> R-1
- 分别求最大值，最小值
代码
Python代码：
"""
@Author: Li Zenghui
@Date: 2020-08-25 14:28
"""
def get_mod(x):
return (x % 10 + 10) % 10
n, m = map(int, input().split())
INF = 1e6
a = []
s = [0]
for _ in range(n):
a.append(int(input()))
a = a + a
for i in range(len(a)):
s.append(s[-1] + a[i])
lenv = len(a)
f = [[[float('inf')] * (m + 1) for _ in range(lenv + 1)] for _ in range(lenv + 1)]
g = [[[float('-inf')] * (m + 1) for _ in range(lenv + 1)] for _ in range(lenv + 1)]
# 枚举区间长度
for _len in range(1, n + 1):
for i in range(0, lenv - _len + 2):
r = i + _len - 1
f[i][r][1] = get_mod(s[r] - s[i-1])
g[i][r][1] = get_mod(s[r] - s[i-1])
for k in range(2, m+1):
for j in range(i + k - 2, r):
f[i][r][k] = min(f[i][r][k], f[i][j][k - 1] * get_mod(s[r] - s[j]))
g[i][r][k] = max(g[i][r][k], g[i][j][k - 1] * get_mod(s[r] - s[j]))
minv, maxv = float('inf'), float('-inf')
for i in range(1, n+1):
minv = min(minv, f[i][i + n-1][m])
maxv = max(maxv, g[i][i + n-1][m])
print(minv)
print(maxv)
C++代码：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 110, M = 10, INF = 0x3f3f3f3f;
int f[N][N][M];
int g[N][N][M];
int n, m;
int w[N], s[N];
int get_mod(int x)
{
return (x % 10 + 10) % 10;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> w[i];
w[i + n] = w[i];
}
for (int i = 1; i <= n * 2; i++) s[i] = s[i - 1] + w[i];
memset(f, 0x3f, sizeof f);
memset(g, -0x3f, sizeof g);
for (int len = 1; len <= n; len++)
{
for (int l = 1; l + len - 1 <= 2 * n; l++)
{
int r = l + len - 1;
f[l][r][1] = g[l][r][1] = get_mod(s[r] - s[l - 1]);
for (int k = 2; k <= m; k++)
{
for (int j = l + k - 2; j < r; j++)
{
f[l][r][k] = min(f[l][r][k], f[l][j][k - 1] * get_mod(s[r] - s[j]));
g[l][r][k] = max(g[l][r][k], g[l][j][k - 1] * get_mod(s[r] - s[j]));
}
}
}
}
int maxv = -INF, minv = INF;
for (int i = 1; i <= n; i++)
{
minv = min(minv, f[i][i + n - 1][m]);
maxv = max(maxv, g[i][i + n - 1][m]);
}
cout << minv << endl;
cout << maxv << endl;
return 0;
}
字符串
1. 最长公共子序列
给定两个长度分别为N和M的字符串A和B，求既是A的子序列又是B的子序列的字符串长度最长是多少。
输入格式
第一行包含两个整数N和M。
第二行包含一个长度为N的字符串，表示字符串A。
第三行包含一个长度为M的字符串，表示字符串B。
字符串均由小写字母构成。
输出格式
输出一个整数，表示最大长度。
数据范围
1≤N,M≤10001≤N,M≤1000
输入样例：
4 5
acbd
abedc
输出样例：
3
思路 
代码
Python代码：
def max_length(s1, s2):
n = len(s1)
m = len(s2)
dp = [[0] * (m+1) for _ in range(n+1)]
if s1[0] == s2[0]:
dp[0][0] = 1
for i in range(1, n+1):
for j in range(1, m+1):
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
if s1[i-1] == s2[j-1]:
dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1)
print(dp)
return dp[n][m]
if __name__ == '__main__':
print(max_length("acbd", "abedc"))
2. 编辑距离
描述 
思路 
代码
Python代码：
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
n1 = len(word1)
n2 = len(word2)
dp = [[0] * (n2 + 1) for _ in range(n1 + 1)]
# 第一行
for j in range(1, n2 + 1):
dp[0][j] = dp[0][j-1] + 1
# 第一列
for i in range(1, n1 + 1):
dp[i][0] = dp[i-1][0] + 1
for i in range(1, n1 + 1):
for j in range(1, n2 + 1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1] ) + 1
#print(dp)
return dp[-1][-1]
Java代码：
class Solution {
public int minDistance(String s1, String s2) {
int m = s1.length();
int n = s2.length();
int[][] dp = new int[m+1][n+1];
for(int i = 0; i <= m; i++) {
dp[i][0] = i;
}
for (int i = 0; i <= n; i++) {
dp[0][i] = i;
}
for (int i = 1; i <= m; i++){
for (int j = 1; j <= n; j++) {
if (s1.charAt(i-1) == s2.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1];
} else {
dp[i][j] = Math.min(Math.min(dp[i-1][j-1], dp[i-1][j]), dp[i][j-1]) + 1;
}
}
}
return dp[m][n];
}
}
树形DP
1. 打家劫舍III
描述 
思路
树形DP
第 1 步：状态定义
dp[node][j] ：这里 node 表示一个结点，以 node 为根结点的树，并且规定了 node 是否偷取能够获得的最大价值。
j = 0 表示 node 结点不偷取；
j = 1 表示 node 结点偷取。
第 2 步： 推导状态转移方程
根据当前结点偷或者不偷，就决定了需要从哪些子结点里的对应的状态转移过来。
如果当前结点不偷，左右子结点偷或者不偷都行，选最大者；
如果当前结点偷，左右子结点均不能偷。
（状态转移方程的表述有点复杂，请大家直接看代码。）
第 3 步： 初始化
一个结点都没有，空节点，返回 0，对应后序遍历时候的递归终止条件；
第 4 步： 输出
在根结点的时候，返回两个状态的较大者。
第 5 步： 思考优化空间
这里空间没有优化的必要。
代码
Java代码：
class Solution {
public int rob(TreeNode node) {
int[] res = dfs(node);
return Math.max(res[0], res[1]);
}
public static int[] dfs(TreeNode node) {
if (node == null) return new int[]{0, 0};
int[] left = dfs(node.left);
int[] right = dfs(node.right);
int[] dp = new int[2];
dp[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
dp[1] = node.val + left[0] + right[0];
return dp;
}
}
Python代码：
class Solution:
def rob(self, root: TreeNode) -> int:
def robInternal(root):
if not root:
return [0, 0]
res = [0, 0]
left = robInternal(root.left)
right = robInternal(root.right)
res[0] = max(left[0], left[1]) + max(right[0], right[1])
res[1] = left[0] + right[0] + root.val
return res
result = robInternal(root)
return max(result[0], result[1])
数位DP
常用技巧：
- 1、题目一般都是问，某一个区间内满足某一条件的个数。
- 2、 [X, Y] = f[y] - f[x-1]
- 3、从树的角度来考虑
4、解题模板
- 初始化f[N][N]或者f[N][N][M]，先判断总位数为1的情况
然后递推，预处理
for (int i = 0; i <= 9; i++) { if (i != 4) { f[1][i] = 1; } } for (int i = 2; i < N; i++) { for (int j = 0; j <= 9; j++) { if (j == 4) continue; for (int k = 0; k <= 9; k++) { if (k == 4 || (j == 6 && k == 2)) continue; f[i][j] += f[i-1][k]; } } }处理dp, 判断n = 0的情况是否满足情况。
- 取得各数位的数字，
- 从最高为nums.size()-1开始枚举，然后枚举 0 <= j <= 9，根据预处理的dp数组求res
- 记得更新last，和x 不满足题意时就直接break;
- 返回 res;
1. 度的数量
2. 数字游戏
输出样例：
思路9 18
f[i][j] 表示一共有 i 位，最高为填j 的个数。
- 初始化 f
- 答案即为 dp(r) - dp(l-1)
代码
Java代码：
package dp.numbergame;
import java.util.*;
public class Solution {
public static int N = 15;
public static int[][] f = new int[N][N];
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
init();
int l, r;
while (in.hasNext()) {
l = in.nextInt();
r = in.nextInt();
System.out.println(dp(r) - dp(l-1));
}
}
private static void init() {
for (int i = 0; i <= 9; i++) {
f[1][i] = 1;
}
for (int i = 2; i < N; i++) {
for (int j = 0; j <= 9; j++) {
for (int k = j; k <= 9; k++) {
f[i][j] += f[i-1][k];
}
}
}
}
private static int dp(int n) {
if (n == 0) return 1;
List<Integer> nums = new ArrayList<>();
while(n > 0) {
nums.add(n % 10);
n /= 10;
}
int res = 0;
int last = 0;
for (int i = nums.size() - 1; i >= 0; i--) {
int x = nums.get(i);
for (int j = last; j < x; j++) {
res += f[i+1][j];
}
if (x < last) break;
last = x;
if (i <= 0) {
res++;
}
}
return res;
}
}
C++代码：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 110, M = 10, INF = 0x3f3f3f3f;
int f[N][N][M];
int g[N][N][M];
int n, m;
int w[N], s[N];
int get_mod(int x)
{
return (x % 10 + 10) % 10;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> w[i];
w[i + n] = w[i];
}
for (int i = 1; i <= n * 2; i++) s[i] = s[i - 1] + w[i];
memset(f, 0x3f, sizeof f);
memset(g, -0x3f, sizeof g);
for (int len = 1; len <= n; len++)
{
for (int l = 1; l + len - 1 <= 2 * n; l++)
{
int r = l + len - 1;
f[l][r][1] = g[l][r][1] = get_mod(s[r] - s[l - 1]);
for (int k = 2; k <= m; k++)
{
for (int j = l + k - 2; j < r; j++)
{
f[l][r][k] = min(f[l][r][k], f[l][j][k - 1] * get_mod(s[r] - s[j]));
g[l][r][k] = max(g[l][r][k], g[l][j][k - 1] * get_mod(s[r] - s[j]));
}
}
}
}
int maxv = -INF, minv = INF;
for (int i = 1; i <= n; i++)
{
minv = min(minv, f[i][i + n - 1][m]);
maxv = max(maxv, g[i][i + n - 1][m]);
}
cout << minv << endl;
cout << maxv << endl;
return 0;
}
3. windy数
思路
- 先求出0 - N之间满足windy数的个数。
- f[i, j] 表示一共有 i 位，并且最高位为 j 的 windy数个数。
代码
Java代码：
package dp.windynumber;
import java.util.*;
public class Main {
public static int N = 11;
public static int[][] f = new int[N][10];
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
init();
int l, r;
l = in.nextInt();
r = in.nextInt();
System.out.println(dp(r) - dp(l - 1));
}
private static int dp(int n) {
if (n == 0) return 0;
// 记录各位的数目
List<Integer> nums = new ArrayList<>();
while (n > 0) {
nums.add(n % 10);
n = n / 10;
}
int res = 0;
int last = -2;
for (int i = nums.size()-1; i >= 0; i--) {
// 最高位
int x = nums.get(i);
// 当前位的数比x小，且与last绝对值之差大于等于2
for (int j = (i == nums.size() - 1? 1 : 0); j < x; j++) {
if (Math.abs(j - last) >= 2) {
// 包括当前位，最高位为j的总windy数
res += f[i+1][j];
}
}
// 如果当前的数和上一位的数，之差大于 2
if (Math.abs(x - last) >= 2) last = x;
else break;
if (i <= 0) res++;
}
// 特殊处理有前导0的数，因为上面其实是没考虑有前导0的情况，但是实际上 0000369 === 369也是属于符合题意的一种情况。
for (int i = 1; i < nums.size(); i++) {
for (int j = 1; j <= 9; j++) {
res += f[i][j];
}
}
return res;
}
private static void init() {
for (int i = 0; i <= 9; i++) {
f[1][i] = 1;
}
for (int i = 2; i < N; i++) {
for (int j = 0; j <= 9; j++) {
for (int k = 0; k <= 9; k++) {
if (Math.abs(k - j) >= 2) {
f[i][j] += f[i-1][k];
}
}
}
}
}
}
4.数字游戏II
5.不要62
思路
- 题目就是求区间内，不满足62和4的个数
- f[i, j] 表示 位数为i , 最高位为 j中满足（not 62 and 4）题意的方案数。
- 递推关系： f[i,j] = f[i-1, k] 其中 j, k不能为4， jk !=62。
- 一定要注意last的处理 ```java package dp.not62; import java.util.*;
public class Main { public static int N = 9; public static int[][] f; public static void main(String[] args) { Scanner in = new Scanner(System.in); int l, r; while (in.hasNext()) { f = new int[N][10]; l = in.nextInt(); r = in.nextInt(); if (l == 0 && r == 0) break; init(); System.out.println(dp(r) - dp(l-1)); } }
private static int dp(int n) {
if (n == 0) return 1;
List<Integer> nums = new ArrayList<>();
while (n > 0) {
nums.add(n % 10);
n = n / 10;
}
int res = 0;
int last = 0;
for (int i = nums.size() - 1; i >= 0; i--) {
int x = nums.get(i);
for (int j = 0; j < x; j++) {
if (j == 4 || (last == 6 && j == 2)) continue;
res += f[i+1][j];
}
if (x == 4 || (last == 6 && x == 2)) break;
last = x;
if (i == 0) res ++;
}
return res;
}
private static void init() {
for (int i = 0; i <= 9; i++) {
if (i != 4) {
f[1][i] = 1;
}
}
for (int i = 2; i < N; i++) {
for (int j = 0; j <= 9; j++) {
if (j == 4) continue;
for (int k = 0; k <= 9; k++) {
if (k == 4 || (j == 6 && k == 2)) continue;
f[i][j] += f[i-1][k];
}
}
}
}
}
```
若有收获，就点个赞吧
0 人点赞
