算法:动态规划


四月的第三周,来学习动态规划。

本来上篇博文的题目叫做《回溯与动态规划》,结果我高估了自己的算法能力,根本学不透hhh,这周来学习动态规划,努力把都所有变种都学会并熟练使用。


动态规划(Dynamic programming,简称DP),是一种拆分问题变成相对简单的子问题的算法。我一直觉得这种算法跟高中的数学归纳法有相似之处:在思考问题时,都是思考怎么从第 N 步推出第 N+1 步,在写答案时,都是先写出第 1 步,然后写第 N 步到第 N +1 步的过程,最终输出结论。这种从第 N 步推到第 N+1 步的过程,在算法中称为“重叠子问题”,就是怎么把问题转换成子问题,通常重叠子问题就是解答的核心问题。

动态规划的核心在于写出递推公式,也就是怎么从第 n 步推到第 n+1 步(这个公式的术语叫做状态转移方程),只要能写出这个递推公式,一般问题就不大了。而写出这个公式的通常做法在于画格子,自己画一个表格,每一行新增一个物品/一天/一个数字,自行观察总结新增了一个之后,怎么从上一行信息得出本行信息。

我觉得自己上篇整理算法的方式是错误的,熟练运用算法最重要的不是理解模板,而是大量的练习。本文不再讲解具体内容了,只简单整理 10 道动态规划的题目(题目描述也不抄了,点击题目能跳转过去),画出表格,写出递推公式。


LeetCode53 最大子序和

物品[-2, 1, -3, 4, -1, 2, 1, -5, 4] 背包容量1 1
-2 -2
-2, 1 1
-2, 1, -3 -2
-2, 1, -3, 4 4
-2, 1, -3, 4, -1 3
-2, 1, -3, 4, -1, 2 5
-2, 1, -3, 4, -1, 2, 1 6
-2, 1, -3, 4, -1, 2, 1, -5 1
-2, 1, -3, 4, -1, 2, 1, -5, 4 5
1
2
dp(i,1) = max( dp(i-1,1) + nums[i], nums[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
public int maxSubArray(int[] nums) {
// 物品个数:nums.length
int len = nums.length;
if (len == 0) {
return 0;
}

// 创建dp数组
int[] dp = new int[len];

// 记录结果
int max = nums[0];

// 遍历数组,dp[i] = (dp[i-1] + num) || (num)
for (int i = 0; i < len; i++) {
if (i > 0) {
dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
} else {
dp[i] = nums[i];
}
max = Math.max(max, dp[i]);
}
return max;
}

LeetCode416 分割等和子集

物品[1, 2, 3, 4] 背包容量5 0 1 2 3 4 5
1
1, 2
1, 2, 3
1, 2, 3, 4
1
2
dp(i,j) = (j == nums[i]) || (dp(i-1,j)) || (dp[i - 1][j - nums[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
public boolean canPartition(int[] nums) {
// 校验数据
int len = nums.length, sum = 0;
if (len == 0) {
return false;
}
for (int num : nums) {
sum += num;
}
if (sum % 2 != 0) {
return false;
}

// 物品个数:nums.length
// 背包容量:总和/2
int itemCount = len;
int capacity = sum / 2;
boolean[][] dp = new boolean[itemCount][capacity + 1];

// 遍历
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < capacity + 1; j++) {
// 自己本身
if (nums[i] == j) {
dp[i][j] = true;
}
// 拷贝上一行
else if (i > 0 && dp[i - 1][j]) {
dp[i][j] = true;
}
// 自己本身组合上一行
else if (i > 0 && j > nums[i] && dp[i - 1][j - nums[i]]) {
dp[i][j] = true;
}
}
}

return dp[itemCount - 1][capacity];
}

Mi27 石头收藏家

物品[2, 3, 5, 7] 物品价值[1, 5, 2, 4] 背包容量10 0 1 2 3 4 5 6 7 8 9 10
2 1
2,3 1 5 6
2,3,5 1 5 6 3 7 8
2,3,5,7 1 5 6 4 7 5 9
1
2
dp(i,j) = max( value[i],       dp(i-1,j-nums[j])+value[i], dp(i-1,j))
新增物品价值本身 新增物品价值加已有价值 继承上一轮的结果
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
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String line, line1 = null, line2 = null, line3;
while (scan.hasNextLine()) {
line = scan.nextLine().trim();

if (line1 == null) {
line1 = line;
} else if (line2 == null) {
line2 = line;
} else {
line3 = line;

// 读取数据
String[] s1 = line2.split(" ");
String[] s2 = line3.split(" ");
int capacity = Integer.parseInt(line1);
int[] weights = new int[s1.length];
int[] values = new int[s2.length];
for (int i = 0; i < s1.length; i++) {
weights[i] = Integer.parseInt(s1[i]);
values[i] = Integer.parseInt(s2[i]);
}

// 动态规划数组 行:物品数量 列:背包容量
int[][] dp = new int[weights.length][capacity + 1];
List<Integer> history = new ArrayList<>();
int max = 0;

// 初始化
if (weights[0] <= capacity) {
dp[0][weights[0]] = values[0];
history.add(weights[0]);
max = values[0];
}

// 遍历
for (int i = 1; i < weights.length; i++) {
// 先拷贝上一行数据
System.arraycopy(dp[i - 1], 0, dp[i], 0, dp[0].length);
// 结合之前的数据
int newWeight = weights[i];
int newValue = values[i];
int historyNum = history.size();
for (int j = 0; j < historyNum; j++) {
int hWeight = history.get(j);
int hValue = dp[i - 1][hWeight];
int nowHeight = hWeight + newWeight;
if (nowHeight <= capacity) {
dp[i][nowHeight] = Math.max(dp[i - 1][nowHeight], hValue + newValue);
max = Math.max(max, dp[i][nowHeight]);
if (!history.contains(nowHeight)) {
history.add(nowHeight);
}
}
}
// 把本身的数据赋值
if (newWeight <= capacity) {
dp[i][newWeight] = Math.max(dp[i][newWeight], newValue);
max = Math.max(max, dp[i][newWeight]);
history.add(newWeight);
}
}
printArray(dp);

line1 = null;
line2 = null;
line3 = null;
System.out.println(max);
}
}
}

LeetCode188 买卖股票的最佳时机 IV

(这个解法效率比较差,但是能做出来)

物品[3, 2, 6, 5, 0, 3] 背包容量6 0 1 2 3 4 5 6
3
3, 2
3, 2, 6 4 4 4 4 4 4
3, 2, 6, 5 4 4 4 4 4 4
3, 2, 6, 5, 0 4 4 4 4 4 4
3, 2, 6, 5, 0, 3 4 7 7 7 7 7
1
2
dp(i,j) = max( (遍历取最大){dp(i-1,j-1)+nums[i]-nums[k]},       dp(i-1,j) )
k-1天进行j-1次交易 + (第i天的股票 -k天的股票) 不交易,沿用上一天
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
public int maxProfit(int k, int[] prices) {
if (prices == null || prices.length < 1) {
return 0;
}

int days = prices.length;
int saleTimes = Math.min(prices.length, k);
int[][] dp = new int[days + 1][saleTimes + 1];

// 第i天进行j次交易 = (遍历取最大){第k-1天进行j-1次交易 + (第i天的股票 - 第k天的股票)}
for (int i = 0; i <= days; i++) {
for (int j = 0; j <= saleTimes; j++) {
// 第1天交易,肯定赚不到钱
if (i <= 1) {
dp[i][j] = 0;
}
// 交易次数是0,肯定赚不到钱
else if (j == 0) {
dp[i][j] = 0;
} else {
int max = dp[i - 1][j];
for (int m = 1; m < i; m++) {
max = Math.max(max, dp[m - 1][j - 1] + (Math.max(prices[i - 1] - prices[m - 1], 0)));
}
dp[i][j] = max;
}
}
}

return dp[days][saleTimes];
}

LeetCode32 最长有效括号

物品[(, (, ), (, ), ), (, )] 背包容量1 1
( 0
(( 0
(() 1
(()( 1
(()() 2
(()()) 3
(()())( 3
(()())() 4
1
2
dp(i)  =  dp(i-2) + 2   ||   dp(i-1) + 2 + dp(i-dp(i-1)-2)
"()"结尾 "))"结尾 (dp(i-dp(i-1)-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
28
29
30
31
32
33
34
35
public int longestValidParentheses(String s) {
// 校验
if (s == null || s.length() < 2) {
return 0;
}

char[] brackets = s.toCharArray();
int[] dp = new int[brackets.length];
int max = 0;

// 遍历符号
for (int i = 1; i < brackets.length; i++) {
if (brackets[i] == ')') {
int already = 0;
// ()结尾,则是dp[i-2]+2
if (brackets[i - 1] == '(') {
if (i >= 2) {
already = dp[i - 2];
}
dp[i] = already + 2;
// ))结尾,则先判断是否成立,如果成立,在上个成立点的基础上+2
} else {
if (i - dp[i - 1] - 1 >= 0 && brackets[i - dp[i - 1] - 1] == '(') {
if (i - dp[i - 1] - 2 >= 0) {
already = dp[i - dp[i - 1] - 2];
}
dp[i] = dp[i - 1] + 2 + already;
}
}
max = Math.max(max, dp[i]);
}
}

return max;
}

LeetCode44 通配符匹配

物品[*, a, *, b] 背包容量 5 a d c e b
*
*, a × × × ×
*, a, *
*, a, *, b × × × ×
1
2
dp(i,j) = dp(i-1,j-1) || dp(i-1,j-1) || { dp(i-1,j) || dp(i,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
32
33
34
35
36
37
38
39
40
41
42
43
public boolean isMatch(String s, String p) {
if (s == null || p == null) {
return false;
}

// 预先过滤一遍"*",多个连续的*缩减成一个
String t = "";
for (char pChar : p.toCharArray()) {
if (pChar != '*') {
t += pChar;
} else if (t.equals("")) {
t += pChar;
} else if (t.charAt(t.length() - 1) != '*') {
t += pChar;
}
}

int m = s.length();
int n = t.length();

// 状态 dp[i][j] : 表示 s 的前 i 个字符和 p 的前 j 个字符是否匹配
boolean[][] dp = new boolean[m + 1][n + 1];

// 初始化
dp[0][0] = true;
for (int i = 1; i <= n; i++) {
dp[0][i] = dp[0][i - 1] && t.charAt(i - 1) == '*';
}

// 状态转移
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s.charAt(i - 1) == t.charAt(j - 1) || t.charAt(j - 1) == '?') {
dp[i][j] = dp[i - 1][j - 1];
} else if (t.charAt(j - 1) == '*') {
dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
}
}
}

// 返回结果
return dp[m][n];
}

LeetCode62 不同路径

1 2 3 4 5 6 7
1 1 1 1 1 1 1 1
2 1 2 3 4 5 6 7
3 1 3 6 10 15 21 28
1
2
dp(i,j) = dp(i-1,j) + dp(i,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
public int uniquePaths(int m, int n) {
if (m == 0 || n == 0) {
return 0;
}

int[][] dp = new int[n][m];
dp[0][0] = 1;

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// 主要是处理0的特殊情况
if (i == 0 && j == 0) {
continue;
}
int up = 0, left = 0;
if (i > 0) {
up = dp[i - 1][j];
}
if (j > 0) {
left = dp[i][j - 1];
}
// 核心逻辑就一行代码,上+左
dp[i][j] = up + left;
}
}

return dp[n - 1][m - 1];
}

LeetCode72 编辑距离

null r r, o r, o, s
null 0 1 2 3
h 1 1 2 3
h, o 2 2 1 2
h, o, r 3 2 2 2
h, o, r, s 4 3 3 2
h, o, r, s, e 5 4 4 3
1
2
3
dp(i,j) = n 其中一方是null,采用另一方单词的长度
|| dp(i-1,j-1) 尾字母相同,采用去掉尾字母的dp
|| 1 + min{ dp(i,j-1), dp(i-1,j), dp(i-1,j-1) } 从三种临界状态过来,再+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
public int minDistance(String word1, String word2) {
int n1 = word1.length();
int n2 = word2.length();
if (n1 == 0 || n2 == 0) {
return n1 + n2;
}

int[][] dp = new int[n1 + 1][n2 + 1];
for (int i = 0; i <= n1; i++) {
for (int j = 0; j <= n2; j++) {
// 当其中一个单词为null时,dp为另一个单词的长度
if (i == 0 || j == 0) {
dp[i][j] = i + j;
}
// 当两个单词尾字母相同时,dp(i,j)=dp(i-1,j-1)
else if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
}
// dp(i,j) = 1 + min{ dp(i,j-1), dp(i-1,j), dp(i-1,j-1) } 代表从任意临近状态过来
else {
dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j]));
}
}
}

return dp[n1][n2];
}

LeetCode85 最大矩形

(不好画表格,经过了两次dp,第一次是行,第二次是列)

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
public int maximalRectangle(char[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return 0;
}

int rows = matrix.length, columns = matrix[0].length;
int result = 0;

// 行dp一次
int[][] lineDp = new int[rows][columns];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
if (matrix[i][j] == '0') {
lineDp[i][j] = 0;
} else if (j == 0) {
lineDp[i][j] = 1;
} else {
lineDp[i][j] = lineDp[i][j - 1] + 1;
}
}
}

int[][] dp = new int[rows][columns];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
if (i == 0) {
dp[i][j] = lineDp[i][j];
} else {
int columnMin = lineDp[i][j];
int max = lineDp[i][j];
for (int k = i - 1; k >= 0; k--) {
columnMin = Math.min(columnMin, lineDp[k][j]);
if (columnMin == 0) {
break;
}
// 宽:遍历之后的最小值 高:i和k之间的距离
int width = columnMin;
int high = i - k + 1;
max = Math.max(max, high * width);
}
dp[i][j] = max;
}
result = Math.max(result, dp[i][j]);
}
}

return result;
}

LeetCode279 完全平方数

0
1 1
2 2
3 3
4 1
5 2
6 3
7 4
8 2
9 1
10 2
11 3
12 3
1
2
dp(i) = i   ||  dp(i)     ||    dp(i-1)+1  ||   平方数   || dp(i-平方数)+1 
i1 遍历的上个结果 上个dp+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
32
33
34
35
36
37
38
39
40
public int numSquares(int n) {
if (n <= 0) {
return 0;
}

// 平方数
int[] squares = new int[(int) Math.sqrt(n) + 1];
for (int i = 0; i < squares.length; i++) {
squares[i] = i * i;
}

int[] dp = new int[n + 1];
for (int i = 1; i < dp.length; i++) {
// 遍历平方数
for (int j = 1; j < squares.length && squares[j] <= i; j++) {
// 如果是平方数,那么dp(i)=1
if (i == squares[j]) {
dp[i] = 1;
}
// 如果不是平方数,那么dp(i)= { i || 前一个+1 || dp(i-平方数)+1 }
else {
if (dp[i] == 0) {
dp[i] = min(i, dp[i - 1] + 1, dp[i - squares[j]] + 1);
} else {
dp[i] = min(dp[i], dp[i - 1] + 1, dp[i - squares[j]] + 1);
}
}
}
}

return dp[n];
}

private int min(int... nums) {
int min = nums[0];
for (int num : nums) {
min = Math.min(min, num);
}
return min;
}