Skip to content

Commit f3292e8

Browse files
linwtlinwt
committed
动态规划模板总结
1 parent 8303ef2 commit f3292e8

15 files changed

+158
-78
lines changed

‎leetcode_Java/DoneTitle.txt

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -19,6 +19,7 @@
1919
53. 最大子数组和
2020
55. 跳跃游戏
2121
62. 不同路径
22+
64. 最小路径和
2223
70. 爬楼梯
2324
72. 编辑距离
2425
77. 组合

‎leetcode_Java/Solution0005.java

Lines changed: 18 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -12,9 +12,9 @@ public String longestPalindrome(String s) {
1212
}
1313
int maxLen = 0;
1414
String res = "";
15-
for (int i = 0; i < len; i++) {
16-
for (int j = i + maxLen; j <= len; j++) {
17-
String sub = s.substring(i, j);
15+
for (int l = 0; l < len; l++) {
16+
for (int r = l + maxLen; r <= len; r++) {
17+
String sub = s.substring(l, r);
1818
int subLen = sub.length();
1919
if (isPalindrome(sub) && subLen > maxLen) {
2020
res = sub;
@@ -34,7 +34,6 @@ private boolean isPalindrome(String s) {
3434
l++;
3535
r--;
3636
}
37-
for (int l = 0, r = s.length() - 1; l < r; )
3837
return true;
3938
}
4039

@@ -86,18 +85,21 @@ private int expandAroudCenter(String s, int l, int r) {
8685

8786

8887
/*
89-
动态规划：
90-
1、回文天然具有「状态转移」性质：一个长度大于 2 的回文去掉头尾字符以后，剩下的部分依然是回文。
91-
反之，如果一个字符串头尾两个字符都不相等，那么这个字符串一定不是回文。「动态规划」的方法根据这样的性质得到。
92-
2、动态规划是暴力破解的优化，两者同样需要遍历列举判断所有子串是否为回文串，
93-
区别是暴力破解每次都要对子串单独处理判断是否为回文串，动态规划可以利用之前记录的子串结果直接判断当前子串是否为回文串
94-
3、boolean数组创建时，默认值是false，只需要标记为true的地方即可
95-
4、dp[l][r]表示子串s[l,r]是否为回文子串，l是左区间，r是右区间
96-
5、状态转移方程：dp[l][r] = (s[l] == s[r]) and (r - l < 3 or dp[l + 1][r - 1])
97-
s[l] == s[r] 表示首尾两个字符相等
98-
r - l < 3 表示去掉首尾后剩余0或1个字符时仍是回文。作用包含了1个字符是回文，所以不用初始化dp数组的对角线为true
99-
dp[l + 1][r - 1] 表示去掉首尾后的区间是否回文
100-
6、dp[l][r]是回文时，则比较并记录最长回文串的长度和首尾位置
88+
动态规划：动态规划是暴力破解的优化，两者同样需要遍历列举判断所有子串是否为回文串，区别是暴力破解每次都要对子串单独处理判断是否为回文串，动态规划可以利用之前记录的子串结果直接判断当前子串是否为回文串
89+
1、题目：给你一个字符串 s，找到 s 中最长的回文子串。
90+
2、题目简化：求字符串s的最长回文子串。要先判断子串是否为回文串，再从回文子串中取最长。
91+
3、定义dp数组：dp[l][r]表示子串s[l,r]是否为回文子串，l是左区间，r是右区间
92+
4、状态转移方程：dp[l][r] = (s[l] == s[r]) and (r - l < 3 or dp[l + 1][r - 1])
93+
1）s[l] == s[r] 表示首尾两个字符相等
94+
2）r - l < 3 表示去掉首尾后剩余0或1个字符时仍是回文。作用包含了1个字符是回文，所以不用初始化dp数组的对角线为true
95+
3）dp[l + 1][r - 1] 表示去掉首尾后的区间是否回文
96+
5、初始化：boolean数组创建时，默认值是false，只需要标记为true的地方即可。可以初始化dp数组的对角线为true，即dp[i][i] = true，表示1个字符是回文
97+
6、遍历dp数组填表：一个for遍历子串的右区间，另一个for循环遍历子串的左区间，根据状态转移方程推断计算未知结果并填表，当是回文串时比较并记录最长长度和左右区间位置
98+
7、返回结果：根据遍历时记录的最长回文子串左右区间位置，截取字符串s得到最长回文子串
99+
100+
s: b a b a d
101+
↑ ↑
102+
l r
101103
*/
102104
class Solution {
103105
public String longestPalindrome(String s) {

‎leetcode_Java/Solution0022.java

Lines changed: 7 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -37,8 +37,13 @@ private void dfs(String track, int n, int left, int right) {
3737
由于我们是一步步计算得到N个括号的情况的，所以小于等于N-1个括号的排列组合方式我们是已知的
3838
（用合适的数据结构存储，方便后续调用，且在存储时可利用特定数据结构实现题目某些要求，如排序，去重等），
3939
且P+Q=N-1，P和Q是小于等于N-1的，所以我们能直接得到P个和Q个括号的情况，进而得到N个括号的结果！
40-
2、dp[i]表示i组括号的所有有效组合
41-
3、dp[i] = "(" + dp[p]的组合 + ")" + dp[q]的组合"，其中1+p+q=i，p从0遍历到i-1，q则相应从i-1到0
40+
2、题目：数字n代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。
41+
3、题目简化：求n对括号的所有有效组合
42+
4、定义dp列表：dp[i]表示i对括号的所有有效组合。本题不能用一维或二维数组，而是用二维列表，存放的是字符串对象
43+
5、状态转移方程：dp[i] = "(" + dp[p]的组合 + ")" + dp[q]的组合，其中1+p+q=i，p从0遍历到i-1，q则相应从i-1到0
44+
6、初始化：dp[0]=[""], dp[1]=["()"]
45+
7、遍历dp数组填表：从前向后，第一个for循环用于遍历dp列表未知位置，第二个for循环用于遍历dp列表已知位置，得到已知结果后根据状态转移方程推断计算未知结果并填表
46+
8、返回结果：最后一个状态就是结果
4247
*/
4348
class Solution {
4449
public List<String> generateParenthesis(int n) {

‎leetcode_Java/Solution0042.java

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -61,11 +61,12 @@ private int getMax(int[] height, int start, int end) {
6161
/*
6262
逐列累加雨水，动态规划，时间复杂度优化，空间换时间：
6363
1、为避免重复遍历计算某位置的左右最高柱子，使用dp数组存放最高柱子
64-
2、dpLeft[i]表示i位置左边最高柱子的高度，dpRight[i]表示i位置右边最高柱子的高度
64+
2、定义dp数组：dpLeft[i]表示i位置左边最高柱子的高度，dpRight[i]表示i位置右边最高柱子的高度
6565
3、状态转移方程：
6666
dpLeft[i] = Math.max(dpLeft[i - 1], height[i - 1]);
6767
dpRight[i] = Math.max(dpRight[i + 1], height[i + 1]);
68-
4、遍历顺序：求 左边最高柱子的高度 则 从左往右 遍历，求 右边最高柱子的高度 则 从右往左 遍历
68+
4、初始化：dp[0]=0，不用赋值了
69+
4、遍历dp数组填表：一个for循环遍历dp数组填表，求 左边最高柱子的高度 则 从左往右 遍历，求 右边最高柱子的高度 则 从右往左 遍历
6970
*/
7071
class Solution {
7172
public int trap(int[] height) {

‎leetcode_Java/Solution0053.java

Lines changed: 9 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -43,29 +43,22 @@ public int maxSubArray(int[] nums) {
4343

4444
/*
4545
动态规划思路：
46-
1、dp[i]表示以i结尾子串的最大值
47-
2、初始条件：dp[0] = nums[0]
48-
3、状态转移方程：
49-
if (dp[i - 1] > 0) dp[i] = dp[i - 1] + nums[i];
50-
else dp[i] = nums[i];
51-
4、从dp数组中每个局部最大值获取全局最大值
46+
1、题目：给你一个整数数组 nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组是数组中的一个连续部分。
47+
2、题目简化：求数组nums的具有最大和的连续子数组的和。要先求多个局部连续子数组的最大和，再从多个局部最大中得到全局最大
48+
3、定义dp数组：dp[i]表示以索引i结尾的连续子数组的最大和
49+
4、状态转移方程：dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
50+
5、初始化：dp[0] = nums[0];
51+
6、遍历dp数组填表：一个for循环遍历dp数组，根据状态转移方程推断计算未知结果并填表
52+
7、返回结果：dp数组的最大值就是具有最大和的连续子数组的和
5253
*/
5354
class Solution {
5455
public int maxSubArray(int[] nums) {
5556
int n = nums.length;
5657
int[] dp = new int[n];
5758
dp[0] = nums[0];
5859
for (int i = 1; i < n; i++) {
59-
if (dp[i - 1] > 0) {
60-
dp[i] = dp[i - 1] + nums[i];
61-
} else {
62-
dp[i] = nums[i];
63-
}
60+
dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
6461
}
65-
int res = dp[0];
66-
for (int i = 1; i < n; i++) {
67-
res = Math.max(res, dp[i]);
68-
}
69-
return res;
62+
return Arrays.stream(dp).max().getAsInt();
7063
}
7164
}

‎leetcode_Java/Solution0055.java

Lines changed: 7 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -3,9 +3,13 @@
33

44
/*
55
动态规划：
6-
1、dp[i]定义：表示在索引为 i 的位置能够跳跃到的最远距离
7-
2、状态转移方程：dp[i] = max(dp[i - 1], i + nums[i])
8-
3、在状态转移前后进行跳跃长度判断以快速得出结果，没希望跳过去、已经足够跳过去
6+
1、题目：给定一个非负整数数组nums，你最初位于数组的第一个下标，数组中的每个元素代表你在该位置可以跳跃的最大长度，判断你是否能够到达最后一个下标。
7+
2、题目简化：求索引 i 位置可以跳跃的最大长度，该长度是否大于等于最后一个索引位置
8+
3、定义dp数组：dp[i]表示索引 i 位置能够跳跃到的最大长度
9+
4、状态转移方程：dp[i] = max(dp[i - 1], i + nums[i]);
10+
5、初始化：dp[0] = nums[0];
11+
6、遍历dp数组填表：一个for循环遍历dp数组，根据状态转移方程推断计算未知结果并填表
12+
7、返回结果：在状态转移前后进行跳跃长度判断以快速得出结果，没希望跳过去、已经足够跳过去
913
*/
1014
class Solution {
1115
public boolean canJump(int[] nums) {

‎leetcode_Java/Solution0062.java

Lines changed: 7 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -3,10 +3,13 @@
33

44
/*
55
动态规划二维dp：自底向上
6-
1、dp[i][j]表示到达位置(i,j)的不同路径条数
7-
2、初始化dp，首行首列只有一条路径，初始化为1
8-
3、状态转移方程：dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 即上方和左方的不同路径条数相加
9-
4、遍历每个位置，记录不同路径条数，直到终点，获得结果
6+
1、题目：一个机器人位于一个 m x n 网格的左上角，机器人每次只能向下或者向右移动一步，机器人试图达到网格的右下角，问总共有多少条不同的路径？
7+
2、题目简化：求从(0,0)到(m-1,n-1)的不同路径条数
8+
3、定义dp数组：dp[i][j]表示到达位置(i,j)的不同路径条数
9+
4、状态转移方程：dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 即上方和左方的不同路径条数相加
10+
5、初始化：首行首列只有一条路径，初始化为1
11+
6、遍历dp数组填表：两个for循环遍历二维dp数组每个位置，根据状态转移方程计算该位置不同路径条数并填表，直到终点，获得结果
12+
7、返回结果：最后一个状态就是结果
1013
*/
1114
class Solution {
1215
public int uniquePaths(int m, int n) {

‎leetcode_Java/Solution0064.java

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
// 64. 最小路径和
2+
3+
4+
/*
5+
动态规划：
6+
1、题目：给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。
7+
2、题目简化：求从 (0,0) 到达 (m-1,n-1) 位置的最小路径和
8+
3、定义dp数组：本题可以直接在原数组操作。grid[i][j] 表示到达 (i,j) 位置的最小路径和
9+
4、状态转移方程：grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]); 即上方或左方的最小路径和
10+
5、初始化：首行首列的路径和进行累加初始化
11+
6、遍历顺序：两个for循环遍历二维dp数组每个位置，根据状态转移方程计算该位置的最小路径和并填表，直到终点，获得结果
12+
*/
13+
class Solution {
14+
public int minPathSum(int[][] grid) {
15+
int n = grid.length, m = grid[0].length;
16+
for (int i = 1; i < n; i++) {
17+
grid[i][0] += grid[i - 1][0];
18+
}
19+
for (int j = 1; j < m; j++) {
20+
grid[0][j] += grid[0][j - 1];
21+
}
22+
for (int i = 1; i < n; i++) {
23+
for (int j = 1; j < m; j++) {
24+
grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
25+
}
26+
}
27+
return grid[n - 1][m - 1];
28+
}
29+
}

‎leetcode_Java/Solution0072.java

Lines changed: 12 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -3,23 +3,30 @@
33

44
/*
55
动态规划：自底向上
6-
1、dp[i][j] 表示 word1 前 i 个字符转换成 word2 前 j 个字符使用的最少操作数
7-
注意第 i 个字符在字符串中为 word1.charAt(i - 1)，索引从0开始
8-
2、初始化：
6+
1、题目：给你两个单词word1和word2，请返回将word1转换成word2所使用的最少操作数。你可以对一个单词进行如下三种操作：插入一个字符、删除一个字符、替换一个字符
7+
2、题目简化：字符串word1转换字符串word2的最少操作数
8+
3、定义dp数组：
9+
1）dp[i][j] 表示 word1 前 i 个字符转换成 word2 前 j 个字符使用的最少操作数
10+
2）扩增dp数组，int[][] dp = new int[n+1][m+1]，dp[0][0]表示两个都是空字符，首行首列表示至少其中一个字符串为空字符的情况
11+
3）注意第 i 个字符在字符串中为 word1.charAt(i - 1)，索引从0开始
12+
4、初始化：
913
1）针对首行首列要单独考虑，引入''。列表示word1，行表示word2
1014
2）第一行是word1为空，word1转换成word2使用的最少操作数，就是插入操作
1115
3）第一列是word2为空，word1转换成word2使用的最少操作数，就是删除操作
12-
3、状态转移方程：
16+
4）首行首列操作数进行累加初始化
17+
5、状态转移方程：
1318
1）当 word1[i] == word2[j]，由于遍历到了i、j，说明 word1 的 0~i-1 和 word2 的 0~j-1 的匹配结果已经生成，当前两个字符相同，无需任何操作，因此 dp[i][j] = dp[i - 1][j - 1];
1419
2）当 word1[i] != word2[j]
1520
① 替换：word1 的 0~i-1 位置与 word2 的 0~j-1 位置的字符都相同，只是当前位置的字符不匹配,进行替换操作后两者变得相同，因此 dp[i][j] = dp[i - 1][j - 1] + 1;
1621
② 删除：若此时 word1 的 0~i-1 位置与 word2 的 0~j 位置已经匹配了，此时多出了 word1 的 i 位置字符，应把它删除掉两者才变得相同，因此 dp[i][j] = dp[i - 1][j] + 1;
1722
③ 插入：若此时 word1 的 0~i 位置只是和 word2 的 0~j-1 位置匹配，此时只需要在 word1 的 i 位置后面插入一个和 word2 的 j 位置相同的字符，使得两者变得相同，因此 dp[i][j] = dp[i][j - 1] + 1;
1823
注：加1表示执行一次操作
19-
4、以 word1 为 "horse"，word2 为 "ros"，且 dp[5][3] 为例，即要将 word1 的前 5 个字符转换为 word2 的前 3 个字符，也就是将 horse 转换为 ros，因此有：
24+
6、以 word1 为 "horse"，word2 为 "ros"，且 dp[5][3] 为例，即要将 word1 的前 5 个字符转换为 word2 的前 3 个字符，也就是将 horse 转换为 ros，因此有：
2025
1）dp[i-1][j-1] 表示替换操作，即先将 word1 的前 4 个字符 hors 转换为 word2 的前 2 个字符 ro，然后将 word1 第五个字符替换成 word2 的第三个字符，即由 e 替换为 s
2126
2）dp[i][j-1] 表示删除操作，即先将 word1 的前 5 个字符 horse 转换为 word2 的前 2 个字符 ro，然后在末尾插入一个 s
2227
3）dp[i-1][j] 表示插入操作，即先将 word1 的前 4 个字符 hors 转换为 word2 的前 3 个字符 ros，然后删除 word1 的第 5 个字符
28+
7、遍历dp数组填表：两个for循环遍历二维dp数组每个位置，根据状态转移方程计算该位置的最少操作数
29+
8、返回结果：最后一个状态就是结果
2330
2431
'' r o s
2532
'' 0 1 2 3

‎leetcode_Java/Solution0139.java

Lines changed: 21 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -3,18 +3,22 @@
33

44
/*
55
动态规划：
6-
1、dp[i]表示前i个字符是否能由单词拼出
7-
2、初始化：dp[0] = true，方便递推判断
8-
3、状态转移方程：dp[i] = dp[j] && wordDict.contains(s.substring(j, i))
9-
4、遍历顺序：固定未知位置，由前面已知推断当前结果。固定第i个字符的位置，然后从头开始遍历到i位置，判断s[0,j)和s[j,i)是否能由单词拼出
10-
5、当dp[i]找到一个成功结果时就可以结束循环了
11-
6、i、j的使用：两个for循环中i、j是用于遍历dp数组的，表示dp数组的索引，dp数组的长度比字符串s 大1，用于初始化，字符串s要用i、j时需要根据情况转换成s对应的索引
6+
1、题目：给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s。注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
7+
2、题目简化：字符串s能否由单词列表拼出
8+
3、定义dp数组：dp[i]表示前i个字符是否能由单词拼出
9+
4、状态转移方程：dp[i] = dp[j] && wordDict.contains(s.substring(j, i))
10+
5、初始化：dp[0] = true，表示字符串为空字符时的情况，方便递推判断
11+
6、遍历dp数组填表：
12+
1）解释一：第一个for循环用于遍历dp数组未知位置，第二个for循环用于遍历dp数组已知位置，得到已知结果后根据状态转移方程推断计算未知结果并填表
13+
2）解释二：固定未知位置，由前面已知推断当前结果。固定第i个字符的位置，然后从头开始遍历到i位置，判断s[0,j)和s[j,i)是否能由单词拼出
14+
3）i、j的使用：两个for循环中i、j是用于遍历dp数组的，表示dp数组的索引，dp数组的长度比字符串s 大1，用于初始化，字符串s要用i、j时需要根据情况转换成s对应的索引
15+
7、返回结果：最后一个状态就是结果
1216
13-
dp □□□□□□
14-
索引 012345
15-
s apple
16-
索引 01234
17-
位置 12345
17+
dp □ □ □ □ □ □
18+
dp索引 0 1 2 3 4 5
19+
s a p p l e
20+
s索引 0 1 2 3 4
21+
s位置 1 2 3 4 5
1822
*/
1923
class Solution {
2024
public boolean wordBreak(String s, List<String> wordDict) {
@@ -36,10 +40,13 @@ public boolean wordBreak(String s, List<String> wordDict) {
3640

3741
/*
3842
动态规划：
39-
1、dp[i]表示前i个字符是否能由单词拼出
40-
2、初始化：dp[0] = true，方便递推判断
43+
1、题目简化：字符串s能否由单词列表拼出
44+
2、定义dp数组：dp[i]表示前i个字符是否能由单词拼出
4145
3、状态转移方程：dp[m] = dp[i] && m <= n && s.startsWith(word, i)
42-
4、遍历顺序：固定已知位置，推断后面位置结果。固定第i个字符的位置，且该位置能由单词拼出，然后遍历单词数组，判断扩增一个单词长度的子串是否为s的子串，是则该子串能由单词拼出
46+
4、初始化：dp[0] = true，表示字符串为空字符时的情况，方便递推判断
47+
5、遍历dp数组填表：
48+
1）解释一：第一个for循环用于遍历dp数组，第二个for循环用于遍历单词数组，根据状态转移方程推断计算未知结果并填表
49+
2）解释二：固定已知位置，推断后面位置结果。固定第i个字符的位置，且该位置能由单词拼出，然后遍历单词数组，判断扩增一个单词长度的子串是否为s的子串，是则该子串能由单词拼出
4350
*/
4451
class Solution {
4552
public boolean wordBreak(String s, List<String> wordDict) {

‎leetcode_Java/Solution0152.java

Lines changed: 10 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -26,10 +26,19 @@ public int maxProduct(int[] nums) {
2626

2727
/*
2828
动态规划：
29-
1、dpMax[i]表示以i位置结尾的子数组最大乘积，dpMin[i]表示以i位置结尾的子数组最小乘积
29+
1、题目：给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
30+
2、题目简化：求数组的最大乘积
31+
3、定义dp数组：dpMax[i]表示以i位置结尾的子数组最大乘积，dpMin[i]表示以i位置结尾的子数组最小乘积。由于存在负数，因此要保留当前的最大最小值。
32+
4、状态转移方程：
33+
dpMax[i] = Math.max(nums[i], Math.max(dpMax[i - 1] * nums[i], dpMin[i - 1] * nums[i]));
34+
dpMin[i] = Math.min(nums[i], Math.min(dpMax[i - 1] * nums[i], dpMin[i - 1] * nums[i]));
35+
5、初始化：dpMax[0] = dpMin[0] = nums[0];
36+
6、遍历dp数组填表：一个for循环遍历dp数组的未知位置，根据状态转移方程直接取dp数组的已知结果计算未知结果
37+
7、返回结果：dpMax[i]中取最大值
3038
*/
3139
class Solution {
3240
public int maxProduct(int[] nums) {
41+
int n = nums.length;
3342
int res;
3443
int[] dpMax = new int[n];
3544
int[] dpMin = new int[n];

0 commit comments

Comments
 (0)