动态规划专题

algorithm

Dynamic Programming

* 动态规划是一种用来解决一类最优化问题的算法思想
* 动态规划将一个复杂问题分解成若干子问题，通过综合子问题的最优解来求得原问题最优解
* 动态规划会将每个求解过的子问题的解记录下来，这样当下一次碰到同样子问题时，就可以直接使用之前记录的结果，而不是重复计算
* 状态的无后效性：当前状态记录了历史信息，一旦当前状态确定，就不会改变，且未来的决策只能在已有的一个或若干个状态的基础上进行，
  历史信息只能通过已有的状态去影响未来的决策。
* 一个问题必须拥有"重叠子问题"和"最优子结构"，才能用动态规划解决。
* 重叠子问题：如果一个问题可以被分解为若干个子问题，且这些子问题会重复出现。
* 最优子结构：如果一个问题的最优解可以由其子问题的最优解有效地构造出来，那么称为这个问题拥有的最优子结构。
  最优子结构保证了动态规划中的原问题的最优解可以由子问题的最优解推导而来。
* 分治与动态规划：分治和动态规划都是将问题分解为子问题，然后合并子问题的解得到原问题的解，
  但是不同的是，分治法分解出的子问题时不重叠的，因此分治法解决的问题不拥有重叠子结构，而动态规划解决的问题拥有重叠子结构。
* 贪心与动态规划：贪心和动态规划都要求原问题必须拥有最优子结构。二者的区别在于，
  贪心直接选择一个子问题去求解，会抛弃一些子问题，这种选择的正确性需要用归纳法证明，而动态规划会考虑所有的子问题。
* 动态规划的核心是"如何设计状态和状态转移方程"。

递归法和递推法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
递归写法（记忆化搜索）
斐波那契(Fibonacci)数列
//T(n) = O(2^n)
int F(int n) {
	if(n == 0 || n == 1) return 1;
	else return F(n-1) + F(n-2);
}

dp[n]记录F[n]的结果，并用dp[n] = -1表示F[n]当前还没有被计算过。
//T(n) = O(n)
int dp[MAXN];
int F(int n) {
	if(n == 0 || n == 1) return 1;
	if(dp[n] != -1) return dp[n];
	else {
		dp[n] = F(n-1) + F(n-2);
		return dp[n];
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
递推写法
数塔问题

令dp[i][j]表示从第i行第j个数字除法的到达最底层的所有路径中能得到的最大和。
则状态转移方程：
	dp[i][j] = max{dp[i+1][j],d[i+1][j+1]} + f[i][j]

#include <cstdio>
#include <algorithm>
uisng namespace std;
const int maxn = 1000;
int f[maxn][maxn], dp[maxn][maxn];
int main() {
	int n;
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= i j++) {
			scanf("%d", &f[i][j]);
		}
	}
	//边界(第n层)
	for(int j = 1; j <= n; j++) {
		dp[n][j] = f[n][j];
	}
	//从第n-1层不断往上计算出dp[i][j]
	for(int i = n - 1; i >= 1; i--) {
		for(int j = 1; j <= i; j++) {
			dp[i][j] = max{dp[i+1][j],d[i+1][j+1]} + f[i][j];
		}
	}
	printf("%d\n", dp[1][1]); //dp[1][1]即为所需要的答案
	return 0;
}

最大连续子序列和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
给定一个数字序列A1,A2,···,An,求i,j（1≤i≤j≤n），使得Ai+···+Aj最大，输出这个最大和
样例：-2 11 -4 13 -5 -2
则最大和为20（11-4+13）

步骤1：令状态dp[i]表示以A[i]作为末尾的连续序列的最大和，以样例为例：序列-2 11 -4 13 -5 -2，下标分别为0,1,2,3,4,5，那么
dp[0] = -2
dp[1] = 11
dp[2] = 7
dp[3] = 20
dp[4] = 15
dp[5] = 13
步骤2：作如下考虑：因为dp[i]要求是必须以A[i]结尾的连续序列，那么只有两种情况：
① 这个最大和的连续序列只有一个元素，即以A[i]开始，以A[i]结尾
② 这个最大和的连续序列有多个元素，即以前面某处A[p]开始(p<i)，一直到A[i]结尾
对第一种情况，最大和就是A[i]本身
对第二种情况，最大和是dp[i-1]+A[i],即A[p]+···+A[i-1]+A[i] = dp[i-1]+A[i]
由于只有两种情况，于是得到状态转移方程:
				dp[i] = max{A[i], dp[i-1]+A[i]}

//T(n) = O(n)
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 10010;
int A[maxn], dp[maxn];
int main() {
	int n;
	scanf("%d", &n);
	for(int i = 0; i < n; i++) {
		scanf("%d", A + i);
	}
	int sum = dp[0] = A[0];
	for(int i = 1; i < n; i++) {
		dp[i] = max(A[i], dp[i-1] + A[i]);
		sum = max(sum, dp[i]);
	}
	printf("%d\n", sum);
}

最长不下降子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
在一个数字序列中，找到一个最长的子序列(可以不连续)，使得这个子序列是不下降(非递减)的。
例如,现有序列A={1,2,3,-1,-2,7,9}(下标从1开始)，它的最长不下降子序列是{1,2,3,7,9}，长度为5

令dp[i]表示以A[i]结尾的最长不下降子序列长度，这样对A[i]来说有两种可能：
① 如果存在A[i]之前的元素A[j]（j<i）使得A[j]≤A[i]且dp[j] + 1 > dp[i]（即
把A[i]跟在以A[j]结尾的LIS后面时能比当前以A[i]结尾的LIS长度更长），那么就把A[i]跟在A[j]结尾的LIS后面，
形成一条更长的不下降子序列(令 dp[i] = d[j] + 1)
② 如果A[i]之前的元素都比，那么A[i]就只好自己形成一条LIS，但是长度为1，即这个子序列里面只有一个A[i]。
最后以A[i]结尾的LIS长度就是①②中能形成的最大长度
由此可以写出状态转移方程：
			dp[i] = max{1, dp[j]+1}
	              (j=1,2,···,i-1 && A[j]＜A[i])

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100;
int A[N], dp[N];
int main() {
	int n;
	scanf("%d", &n);
	for(int i = 1;i <= n; i++) {
		scanf("%d", A + i);
	}
	int ans = -1;  //记录最大的dp[i]
	for(int i = 1; i <= n; i++) {
		dp[i] = 1; //边界初始条件(即先假设每个元素自成一个序列)
		for(int j = 1; j < i; j++) {
			if(A[i] >= A[j] && (dp[j] + 1 > dp[i])) {
				dp[i] = dp[j] + 1;  //状态转移方程，用以更新dp[i]
			}
		}
		ans = max(ans, dp[i]);
	}
	printf("%d", ans);
	return 0;
}

最长公共子序列(LCS)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
给定两个字符串(或数字序列)A 和 B，求一个字符串，使得这个字符串是A和B的最长公共部分(子序列可以不连续)
样例：字符串"sadstory"和"adminsorry"的最长公共子序列为"adsory"长度为6

令dp[i][j]表示字符串A的i号位和字符串B的j号位之前的LCS长度(下标从1开始)，如dp[4][5]表示"sads"与"admin"的LCS长度。那么可以根据A[i]和B[j]的情况，分为两种决策：
① 若A[i] == B[j]，则字符串A与字符串B的LCS增加了1位，即有dp[i][j] = dp[i-1][j-1] + 1。
② 若A[i] ≠ B[j]，则字符串A的i号位和字符串B的j号位之前的LCS无法1延长，因此dp[i][j]将会继承dp[i-1][j]和dp[i][j-1]中的较大值，即有dp[i][j] = max{dp[i-1][j],dp[i]][j-1]}。
由此得到状态转移方程：
		dp[i][j] = dp[i-1][j-1], if A[i] == B[i]
		dp[i][j] = max{dp[i-1][j], dp[i][j-1]}, if A[i] ≠ B[i]
边界：dp[i][0] = dp[0][j] = 0 (0≤i≤n， 0≤j≤m)
最终dp[n][m]即为答案

//T(n) = O(nm);
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100;
char A[N], B[N];
int dp[N][N] = {0};
int main() {
	int n;
	gets(A + 1); gets(B + 1);
	/*
	for(int i = 0; i <= strlen(A + 1); i++) {
		dp[i][0] = 0;
	}
	for(int j = 0; j <= strlen(A + 1); j++) {
		dp[0][j] = 0;
	}
	*/
	for(int i = 1; i <= strlen(A + 1); i++) {
		for(int j = 1; j <= strlen(B + 1); j++) {
			if(A[i] == B[j]) {
				dp[i][j] = dp[i-1][j-1] + 1;
			}else {
				dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
			}
		}
	}
	printf("%d\n", dp[strlen(A + 1)][strlen(B + 1)]);
	return 0;
}

最长回文子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
给出一个字符串s，求S的最长回文子串的长度。
样例：字符串"PATZJUJZTACCBCC"的最长回文子串是"ATZJUJZTA",长度为9。

令dp[i][j]表示S[i]至S[j]所表示的子串是否是回文子串，是则为1，不是为0。
这样根据S[i]是否等于S[j]，可以把转移情况分为两类：
① 若S[i] == S[j]，那么只要S[i+1]至S[j-1]是回文子串，S[i]至S[j]就是回文子串；
如果S[i+1]至S[j-1]不是回文子串。则S[i]至S[j]一定不是回文子串。
② 若S[i] ≠ S[j]，那么S[i]至S[j]一定不是回文子串。
由此可以写出状态转移方程：
		dp[i][j] = dp[i+1][j-1], if S[i] == S[j]
		dp[i][j] = 0, if S[i] ≠ S[j]
边界：dp[i][i] = 1, dp[i][i+1] = (S[i] == S[i+!]) ? 1 : 0

//T(n) = O(n²)
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 1010;
char S[maxn];
int dp[maxn][maxn];
int main() {
	cin.getline(S, maxn);
	int len = strlen(S), ans = -1;
	memset(dp, 0, sizeof(dp));
	//边界
	for(int i = 0; i < len; i++) {
		dp[i][i] = 1;
		if(i < len - 1) {
			if(S[i] == S[i+1]) {
				dp[i][i+1] = 1;
				ans = 2; //当前最长回文子串长度
			}
		}
	}
	//状态转移方程
	for(int L = 3; L <= len; L++) {
		for(int i = 0; i + L -1 < len; i++) {
			int j = i + L - 1; //子串右端点
			if(S[i] == S[j] && dp[i+1][j-1] == 1) {
				dp[i][j] = 1;
				ans = L;
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}

二分+字符串hash T(n) = O(nlogn)
Manacher算法 T(n) = O(n)

DAG最长路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
解决两个问题
① 求整个DAG中的最长路径(不固定起点和终点)
② 固定终点，求DAG的最长路径

第一个问题：给定一个有向无环图，怎样求解整个图的所有路径中权值之和最大的那条。
令dp[i]表示从i号顶点除法能获得的最长路径长度，这样所有dp[i]的最大值就是整个DAG的最长路径长度。
如果从i号顶点出发能直接到达顶点j1,j2,···,jk,而dp[j1], dp[j2], ···,dp[jk]均已知，
那么就有dp[i] = max{dp[j] + length[i->j],(i,j)∈E}
根据上面思路可以按照逆拓扑序列的顺序来求解dp数组
所以我选择递归(｡･ω･｡)

int DP(int i) {
	if(dp[i] > 0) return dp[i];
	for(int j = 0; j < n; j++) {
		if(G[i][j] != INF) {
			dp[i] = max(dp[i], DP[j] + G[i][j]);
		}
	}
	return dp[i];
}

开一个int型choice数组记录最长路径的后继结点，
如果最终有多条路径，将choice数组改为vector类型的数组(Dijkstra算法中有多条路径时的做法)，记得去实现它哦。
还有如何求解最长路径条数。

int DP(int i) {
	if(dp[i] > 0) return dp[i];
	for(int j = 0; j < n; j++) { //遍历i的所有出边
		if(G[i][j] != INF) {
			int temp = DP[i] + G[i][j];
			if(temp > dp[i]) {
				dp[i] = temp;
				choice[i] = j; //i号顶点的后继顶点是j
			}
		}
	}
	return dp[i]; //返回计算完的dp[i]
}
调用printPath前需要先得到最大的dp[i]，然后将i作为路径起点传入
void printPath(int i) {
	printf("%d", i);
	while(choice[i] != -1) { //choice数组初始化为-1
		i = choice[i];
		printf("->%d", i);
	}
}

第二个问题：固定终点，求DAG的最长路径
令dp[i]表示从i号顶点出发到达终点（假设终点为T）能获得的最长路径长度，
同理，如果从i号顶点出发能直接到达顶点j1,j2,···,jk,而dp[j1], dp[j2], ···,dp[jk]均已知，
那么就有dp[i] = max{dp[j] + length[i->j],(i,j)∈E}
边界：dp[T] = 0， so problem is coming， 数组不能初始化为0了
合适做法：初始化dp数组为一个负的大数来保证"无法到达终点"的含义得以表达，然后设置一个vis数组表示顶点是否已经被计算。

int DP(int i) {
	if(vis[i] == true) return dp[i]; //dp[i]已计算得到直接返回，减少重复计算
	vis[i] = true;
	for(int j = 0; j < n; j++) {
		if(G[i][j] != INF) {
			dp[i] = max(dp[i], DP[j] + G[i][j]);
		}
	}
	return dp[i];
}

经典问题：矩形嵌套问题

背包问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
01背包问题：
有n件物品，每件物品的重量为w[i]，价值为c[i]。现有一个容量为V的背包，
问如何选取物品放入背包，使得背包内物品的总价值最大。其中每件物品都只有1件。
样例：
5 8  // n == 5,v == 8
3 5 1 2 2 // w[i]
4 5 2 1 3 // c[i]
T(n) = O(nV)

令dp[i][j]表示前i件物品(1 ≤ i ≤ n，0 ≤ j ≤ v)恰好装入容量为j的背包中所能获得的最大价值。然后求解dp[i][j]：
考虑对第i件物品的选择策略，有两种：
① 不放第i件物品，那么问题转化为前i-1件物品恰好装入容量为j的背包中所能获得的最大价值。也即dp[i-1][j]。
② 放第i件物品，那么问题转化为前i-1件物品恰好装入容量为j-w[i]的背包中所能获得的最大价值。也即dp[i-1][j-w[i]] + c[i]。
因此状态转移方程为：
	dp[i][j] = max{dp[i-1][j], dp[i-1][j-w[i]] + c[i]}
	(1 ≤ i ≤ n，w[i] ≤ j ≤ v)
边界: dp[0][j] = 0（0 ≤ j ≤ v）
答案: dp[n][v]
空间复杂度: O(nv)
for(int i = 1; i <= n; i++) {
	for(int j = 1; j <= v; 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]] + c[i]);
		}
	}
}

优化: 一维: 
	dp[j] = max{dp[j], dp[j-w[i]] + c[i]}
	(1 ≤ i ≤ n，w[i] ≤ j ≤ v)
边界: dp[j] = 0, 0 ≤ j ≤ v
答案: dp[v]
空间复杂度: O(v)
for(int i = 1; i <= n; i++) {
	for(int j = v; j >= w[i]; j--) {
		dp[j] = max(dp[j], dp[j-w[i]] + c[i]);
	}
}
优化版完整代码：
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100;
const int maxv = 1000;
int w[maxn], c[maxn], dp[maxn] = {0};
int main() {
	int n, v;
	scanf("%d%d", &n, &v);
	for(int i = 0; i < n; i++) {
		scanf("%d", w + i);
	}
	for(int i = 0; i < n; i++) {
		scanf("%d", c + i);
	}
	for(int i = 1; i <= n; i++) {
		for(int j = v; j >= w[i]; j--) {
			dp[j] = max(dp[j], dp[j-w[i]] + c[i]);
		}
	}
	printf("%d\n",dp[v]);
	return 0;
}

如果需要知道是哪些物品被放入了背包，可用"回溯算法"(针对未优化版本)
算法思想：
从表的右下角dp[n][v]开始回溯，
如果发现前n个物品最佳组合的价值和前n-1个物品的最佳组合的价值一样，说明第n个物品没有被装入。
否则，第n个物品被装入。
soluton: 增加一个object[], object[i] = true表示第i个物品被装入, false表示没装入。
bool object[maxn] = {false};
void Find(int i, int j) {
	if(i == 0) {
		for(int i = 0; i < n; i++) {
			if(i) printf(" ");
			printf("%d", object[i]);
		}
		return;
	}
	if(dp[i][j] == dp[i-1][j]) { //第i个物品没有被装入
		object[i] = false;
		Find(i-1, j);
	}else { //第i个物品被装入
		object[i] = true;
		Find(i-1,j-w[i]);
	}
}

总结

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
(1)最大连续子序列和
令dp[i]表示以A[i]作为末尾的连续序列的最大和
(2)最长不下降子序列(LIS)
令dp[i]表示以A[i]结尾的最长不下降子序列长度
(3)最长公共子序列(LCS)
令dp[i][j]表示字符串A的i号位和字符串B的j号位之前的LCS长度
(4)最长回文子串
令dp[i][j]表示S[i]至S[j]所表示的子串是否是回文子串
(5)数塔DP
令dp[i][j]表示从第i行第j个数字除法的到达最底层的所有路径上所能得到的最大和
(6)DAG最长路
令dp[i]表示从i号顶点出发能获得的最长路径长度
(7)01背包
令dp[i][v]表示前i件物品恰好装入容量为v的背包中能获得的最大价值。
(8)完全背包
令dp[i][v]表示前i件物品恰好装入容量为v的背包中能获得的最大价值。

(1)-(4): 
当题目与序列或字符串(记为A)有关时，可以考虑把状态设计成下面两种形式，然后根据端点特点去考虑状态转移方程。
	① 令dp[i]表示以A[i]结尾（或开头）的XXX
	② 令dp[i][j]表示A[i]至A[j]区间的XXX
其中XXX均为原问题的表述。

(5)-(8):
状态设计都包含某种"方向"的意思。
分析题目中的状态需要几维来表示，然后对其中的每一维采取下面的某一个表述：
① 恰好为i。
② 前i。
在每一维的含义设置完毕之后，dp数组的含义可以设置成"令dp数组表示恰好为i(或前i)、恰好为j(或前j)······的XXX",
其中XXX为原问题的描述。接下来通过端点的特点去考虑状态转移方程。

注：在大多数情况下，都可以把动态规划可解的问题看做一个DAG，图中的结点就是状态，边就是状态转移的方向，
求解问题的顺序就是按照DAG的拓扑序列求解。

本文标题:动态规划专题

文章作者:Kino

发布时间:2020年03月18日 - 10时07分

最后更新:2020年03月21日 - 08时44分

原始链接:https://cybaol.github.io/2020/03/18/DP/

许可协议: "署名-非商用-相同方式共享 3.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 递归法和递推法
  2. 2. 最大连续子序列和
  3. 3. 最长不下降子序列
  4. 4. 最长公共子序列(LCS)
  5. 5. 最长回文子串
  6. 6. DAG最长路
  7. 7. 背包问题
  8. 8. 总结
,