动态规划（dynamic programming）算法是解决多阶段决策过程最优化问题的一种常用方法，利用动态规划，可以解决很多贪婪算法或分治算活不能解决的。
最核心的思想，就在于拆分子问题，记住过往，减少重复计算。
引入
一个典型的动态规划问题：
求序列 nums = [1,5,2,4,3]的最长递增子序列长度。
直观可以看出最长递增子序列有[1,2,4]或[1,2,3]，长度为3。
暴力枚举/暴力搜索
首先容易想到的就是暴力枚举/暴力搜索方法。
先利用递归分别计算从每个位置出发的子序列，然后取其中长度的最大值。
序列nums = [1,5,2,4,3]，如果从1出发，到5、2、4、3都是递增的，则可得下式（设f(x)为从x出发的最长递增子序列长度）
由此可递归求得，从1出发最长递增子序列长度。
graph TD
A((1))
B((5))
C((2))
D((4))
E((3))
F((4))
G((3))
A-->B;
A-->C;
A-->D;
A-->E;
C-->F;
C-->G;
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
| #include <iostream>
#include <vector>
using namespace std;
int L (vector<int> nums, int i) {
if (i == nums.size() - 1) {
return 1;
}
int max_len = 1;
for (int j = i+1; j < nums.size(); ++j) {
if (nums[j] > nums[i]) {
max_len = max(max_len, L(nums, j) + 1);
}
}
return max_len;
}
int length_of_LIS (vector<int> nums) {
int max_len = 1;
for (int i = 0; i < nums.size(); ++i) {
max_len = max(max_len, L(nums, i));
}
return max_len;
}
int main () {
vector<int> nums = {1,5,2,4,3};
cout << length_of_LIS(nums);
}
|
时间复杂度：
每个子序列都需要遍历一次，判断是否是递增序列，时间复杂度为$O(2^n)$，每个子序列至多遍历n次，总时间复杂度为$O(n*2^n)$。
时间复杂度为指数级别的算法，以下针对这个问题进行优化。
记忆化搜索/剪枝
暴力枚举中存在大量重复计算问题，如下图中在2的子树中遍历了4，后面又遍历了一次4，重复计算了两次。
所以可以用一个哈希表记录已计算的“从i开始的最长子序列长度”，用空间换取时间上的缩短。
graph TD
A((1))
B((5))
C((2))
D((4))
E((3))
F((4))
G((3))
A-->B;
A-->C;
A-->D;
A-->E;
C-->F;
C-->G;
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
| #include <iostream>
#include <vector>
#include <map>
using namespace std;
map<int, int> memo;
int L (vector<int> nums, int i) {
if (memo.count(i)) {
return memo[i];
}
if (i == nums.size() - 1) {
return 1;
}
int max_len = 1;
for (int j = i+1; j < nums.size(); ++j) {
if (nums[j] > nums[i]) {
max_len = max(max_len, L(nums, j) + 1);
}
}
memo[i] = max_len;
return max_len;
}
int length_of_LIS (vector<int> nums) {
int max_len = 1;
for (int i = 0; i < nums.size(); ++i) {
max_len = max(max_len, L(nums, i));
}
return max_len;
}
int main () {
vector<int> nums = {1,5,2,4,3};
cout << length_of_LIS(nums);
}
|
迭代/非递归的实现
将上面的方法归纳成非递归的形式。
序列 nums = [1,5,2,4,3]
可以看出，只要从后往前依次计算，就可以通过迭代方法计算出所有的$L(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
| #include <iostream>
#include <vector>
using namespace std;
int length_of_LIS (vector<int> nums) {
vector<int> L(nums.size(), 1);
for (int i = L.size() - 2; i >= 0; --i) {
for (int j = i+1; j < L.size(); ++j) {
if (nums[j] > nums[i]) {
L[i] = max(L[i], L[j]+1);
}
}
}
int max_length = 1;
for (int l : L) {
if (l > max_length) {
max_length = l;
}
}
return max_length;
}
int main () {
vector<int> nums = {1,5,2,4,3};
cout << length_of_LIS(nums);
}
|
时间复杂度为$O(n^2)$，相比暴力搜索的$O(n*2^n)$，时间大大降低。
动态规划的基本思想和基本概念
基本思想
- 将待求解的问题分解成若干个子问题，层层分解，直到问题可以直接解决
- 对于重复出现的子问题，只在第一次遇到的时候进行求解，并将结果保存起来，下次遇到时直接引用答案
基本概念
- 阶段：把问题分为具有一定次序的若干阶段，即第n个子问题就是第n个阶段。
- 状态：每个阶段开始时所处的状态，即在求第n个阶段的解时，已求得的第n-1个阶段的解，就是当前的状态。
- 决策：目前已知第n-1个阶段的状态，可以通过决策，确定下一个阶段的状态
- 状态转移方程：从第n-1个阶段的状态到第n个阶段的状态的方程
动态规划例题
最长回文子串
求字符串中最长的回文子串，回文子串即左右对称的串，如ABBA、ABCBA。
分析步骤
代码实现
采用迭代的形式，在计算长串的 $dp[i][j]$ 前，必须要已知 $dp[i+1][j-1]$ ，即要保证左下角的状态已求，所以遍历顺序如下，遍历列优先的上三角。
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
| #include <iostream>
#include <vector>
using namespace std;
int length_of_LPS (string str) {
vector<vector<bool>> dp(str.length(), vector<bool>(str.length(), false));
int max_length = 0;
for (int j = 0; j < dp[0].size(); ++j) {
for (int i = 0; i <= j; ++i) {
if (i == j) {
dp[i][j] = true;
} else if (j - i == 1) {
dp[i][j] = str[i] == str[j];
} else {
dp[i][j] = (str[i] == str[j]) && dp[i+1][j-1];
}
if (dp[i][j] && j - i + 1 > max_length) {
max_length = j - i + 1;
}
}
}
return max_length;
}
int main () {
string str;
cin >> str;
cout << length_of_LPS(str) << endl;
}
|
正则表达式匹配
一个字符串 s 和一个字符规律 p，实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。
. 匹配任意单个字符
* 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖整个字符串 s 的，而不是部分字符串。
示例一
输入：
s = “aa”
p = “a*”
输出：
true
解释：因为 * 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此，字符串 “aa” 可被视为 ‘a’ 重复了一次。
示例二
输入：
s = “ab”
p = “.*”
输出：
true
解释：.* 表示可匹配零个或多个（*）任意字符（.）。
提示：
- 1 <= s.length <= 20
- 1 <= p.length <= 30
- s 只包含从 a-z 的小写字母。
- p 只包含从 a-z 的小写字母，以及字符 . 和 *。
- 保证每次出现字符 * 时，前面都匹配到有效的字符
问题分析
关键在于处理'*'问题，'*'需要搭配前面的一个字符使用。如，
状态定义
定义 $dp[i][j]$ 表示s的前i个字符和p的前j个字符是否匹配。
状态转移
如 $p[j]$ 为小写字母
$s[0,i]$ 和 $p[0,j]$ 的匹配问题，可以分解为两个子问题，即 $s[0,i-1]$ 和 $p[0,j-1]$ 匹配，且 $s[i]$ 和 $p[j]$ 相同
如 $p[j]$ 为'.'
只要$s[0,i-1]$ 和 $p[0,j-1]$ 匹配，则$s[0,i]$ 和 $p[0,j]$ 也一定匹配
如 $p[j]$ 为'*'
需要与前一个字符 $p[j-1]$ 一起计算，可对 $p[j-1]$ 匹配 $k$ 次，如"a*"，
匹配 $0$ 次
s = "bc" p = "bca*"
"a*"匹配 $0$ 次，即"a*"相当于""，p = "bca*" 化为 "bc"
匹配 $1$ 次
s = "bca" p = "bca*"
"a*"匹配 $1$ 次，即"a*"相当于"a"
如匹配，则$s[0,i]$一个字符为a，且$s[0,i]$去除掉 $1$ 个a后、$p[0,j]$去除掉 "a*"后，查看是否匹配
匹配 $k$ 次
$s[0,i]$ 和 $p[0,j]$ 的匹配问题，可以分解为
即 $p[j]$ 为'*'时，转移矩阵只要匹配 $0、1…k$ 次有一个成立，则$s[0,i]$ 和 $p[0,j]$ 匹配
匹配 $0$ 次，即 s = "bc" p = "bca*"
匹配 $k$ 次
需要有一个前提，即 $s[i]$ 等于 $p[j-1]$
s = "bcaa" p = "bca*"，如果 $s$ 去掉一个a也匹配，即"bca" "bca*"匹配，则$s[0,i]$ 和 $p[0,j]$ 匹配（如 $p[j-1]=’.’$ ，也相当于 $s[i]=p[j-1]$ 成立）
总状态转移矩阵
初始化
$s$ 的长度为 m，$p$ 的长度为 n，需要考虑空串的匹配问题，所以状态大小设置为$dp[m+1][n+1]$
要求 $dp[i][j]$ 需先有左上角的 $dp[i-1][j-1]$ 、$dp[i][j-2]$ 、$dp[i-1][j]$ ，所以初始化应先求出左边和上边，即$dp[…][0]$ 、$dp[0][…]$
两个空串必然匹配，所以 $dp[0][0] = true$
空串p = ""和任意非空s不匹配，即 $dp[1…n][0] = false$
空串s = ""和奇数长度的p不可能匹配，和偶数长度的p可能匹配，如p = "a*b*c*"，所以当 $p[j] = ‘*’$ 时，$dp[0][j] = dp[0][j-2]$
代码实现
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
| class Solution {
public:
static bool isMatch(string s, string p) {
int n = s.size(), m = p.size();
vector<vector<int>> dp(n+1, vector<int>(m+1, false));
dp[0][0] = true;
for (int j = 2; j <= m && p[j-1] == '*'; j += 2) {
dp[0][j] = true;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s[i-1] == p[j-1] || p[j-1] == '.') {
dp[i][j] = dp[i-1][j-1];
} else if (p[j-1] == '*') {
dp[i][j] = dp[i][j-2] || ((s[i-1] == p[j-2] || p[j-2] == '.') && dp[i-1][j]);
}
}
}
return dp[n][m];
}
};
|
称砝码
现有n种砝码，重量互不相等，分别为 m1,m2,m3…mn ，每种砝码对应的数量为 x1,x2,x3…xn，问能称出多少种不同的重量。（注：称重重量包括 0）
输入描述：
对于每组测试数据：
第一行：n —- 砝码的种数(范围[1,10])
第二行：m1 m2 m3 … mn —- 每种砝码的重量(范围[1,2000])
第三行：x1 x2 x3 …. xn —- 每种砝码对应的数量(范围[1,10])
输出描述：
利用给定的砝码可以称出的不同的重量数
示例一
输入：
2
1 2
2 1
输出：
5
示例二
输入：
3
10 191 103
6 6 5
输出：
254
代码实现
递归实现
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
| #include <iostream>
#include <vector>
#include <set>
#include <map>
using namespace std;
map<vector<vector<int>>, set<int>> memo;
set<int> different_sum(vector<vector<int>> v) {
if (memo.count(v)) {
return memo[v];
}
set<int> s;
int n = 0;
for (int i = 0; i < v.size(); ++i) {
n += v[i][1];
if (v[i][1] != 0) {
break;
}
}
if (n == 0) {
s.insert(0);
return s;
}
for (int i = 0; i < v.size(); ++i) {
if (v[i][1] != 0) {
vector<vector<int>> t = v;
t[i][1] -= 1;
for (int j : different_sum(t)) {
s.insert(j);
s.insert(j + v[i][0]);
}
}
}
memo[v] = s;
return s;
}
int main () {
int n;
cin >> n;
vector<vector<int>> v(n, vector<int>(2, 0));
for (int i = 0; i < 2*n; ++i) {
if (i < n) {
cin >> v[i][0];
} else if (i >= n) {
cin >> v[i-n][1];
}
}
cout << different_sum(v).size() << endl;
}
|
迭代方法
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
| #include <iostream>
#include <vector>
#include <set>
using namespace std;
int main () {
int n;
cin >> n;
vector<vector<int>> v(n, vector<int>(2, 0));
for (int i = 0; i < 2*n; ++i) {
if (i < n) {
cin >> v[i][0];
} else if (i >= n) {
cin >> v[i-n][1];
}
}
set<int> s;
s.insert(0);
bool flag = false;
for (int i = 0; i < n; ++i) {
if (v[i][1] != 0) {
flag = true;
break;
}
}
while (flag) {
for (int i = 0; i < n; ++i) {
if (v[i][1] != 0) {
set<int> s_copy = s;
for (int j : s_copy) {
s.insert(j + v[i][0]);
}
s.insert(v[i][0]);
v[i][1] --;
}
}
flag = false;
for (int i = 0; i < n; ++i) {
if (v[i][1] != 0) {
flag = true;
break;
}
}
}
cout << s.size() << endl;
}
|