动态规划好难！题单：https://leetcode.cn/discuss/post/3581838/fen-xiang-gun-ti-dan-dong-tai-gui-hua-ru-007o/
1. 入门DP
1.1. 爬楼梯
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public int climbStairs(int n) {
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 2] + dp[i - 1];
}
return dp[n];
}
}
|
题目：给你一个由 不同 整数组成的数组 nums，和一个目标整数 target。请你从 nums 中找出并返回总和为 target 的元素排列的个数。
注意，题目说的是求元素排列的个数，因此是一种爬楼梯的题目。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public int combinationSum4(int[] nums, int target) {
int n = nums.length;
int[] dp = new int[target + 1];
Arrays.fill(dp, 0);
dp[0] = 1;
for (int i = 1; i <= target; i++) {
int sum = 0;
for (int j = 0; j < n; j++) {
if (i < nums[j]) { continue; }
sum += dp[i - nums[j]];
dp[i] = sum;
}
}
return dp[target];
}
}
|
1.2. 打家劫舍
1.3. 最大子数组和
这个题还可以用前缀和+买卖股票的思想来做。因为子数组就等于两个前缀和的差，因此就转化为前缀和的股票价格，选两天买和卖。
考虑一下空字符串的价值为0，也可能为最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
private final Map<Character, Integer> mp = new HashMap<>();
public int maximumCostSubstring(String s, String chars, int[] vals) {
for (int i = 0; i < vals.length; i++) {
mp.put(chars.charAt(i), vals[i]);
}
int n = s.length();
int[] dp = new int[n + 1];
dp[0] = this.getValue(s.charAt(0));
int ans = Math.max(dp[0], 0);
for (int i = 1; i < n; i++) {
int val = this.getValue(s.charAt(i));
dp[i] = Math.max(val, dp[i - 1] + val);
ans = Math.max(dp[i], ans);
}
return ans;
}
private int getValue(char c) {
Integer val = mp.get(c);
return val == null ? (c - 'a' + 1) : val;
}
}
|
2. 网格图DP
待补充
3. 背包问题
背包问题不难，难的是边界的考虑。
注意外层循环和内层循环分别是什么。爬楼梯问题求的是“排列个数”，因此外层循环必须是容量，内层循环则在之前容量的基础上再选一个物品；01背包问题求的是“组合个数”，且每个物品只能选1次，放了防止物品多选，外层循环必须是物品个数。完全背包问题两种都可，因为物品可以重复选。
3.1. 01背包
3.2. 完全背包
首先递归方程和**原数据 coins[]**的下标表示，用灵神的方法就是 dp[i+1][j] 表示 coins 取闭区间 [0:i] 和容量为 j 的情况，i 就是从 for(i=0;i<n;i++) 开始遍历的，相当于在 i 的维度上整体右移了一格。
这样就有两个方向的边界需要考虑：
- 物品个数的维度
i：dp[0][j] 实际上在递推中是不被计算的，但在第一轮 dp[i+1][j]=f(d[i][j]) 中会被用到，所以是需要初始化边界的
- 容量的维度
j：dp[i][0] 在递推中也是不被计算的，但也可能会被用到，例如说某个硬币面值刚好等于总金额 dp[][j-coins[i]], j=coins[i]
那么怎么初始化边界呢？得看题目要我们求什么，这个题是求最少的硬币个数，所以上述两个边界问题可以这么考虑：
dp[i][0](i>=0) 表示用 i 个硬币凑出 0，这必然有且仅有一种方案，就是啥也不选，但是此处并非初始化为 1，因为要求的是硬币个数，所以应当初始化为 0；该维度的初始化可以放在每次 j 的循环之前，但是 dp[0][0] 并不会被循环遍历到，所以还是要手动初始化至少 1 个值dp[0][j](j>0) 表示用 0 个硬币凑出 j>0 的硬币个数，很显然这是不可能做到的，是非法的，我们不希望这类各自被后续递推时用到。再看递推方程是取 Math.min() 的，因此我们只需将其初始化为 1 个很大的值，让合法值与非法值相比时，永远取合法值即可；当然也可能是两个非法值取 Math.min()，这样操作后仍为非法值，这是预期之内的；非法值的选择可以用最大值 amount+1，因为不可能用 amount+1 个硬币来凑出 amount
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public int coinChange(int[] coins, int amount) {
int n = coins.length;
int[][] dp = new int[n + 1][amount + 1];
Arrays.fill(dp[0], amount + 1);
dp[0][0] = 0;
for (int i = 0; i < n; i++) {
dp[i + 1][0] = 0;
for (int j = 1; j <= amount; j++) {
dp[i + 1][j] = dp[i][j];
if (coins[i] <= j) {
dp[i + 1][j] = Math.min(dp[i + 1][j], 1 + dp[i + 1][j - coins[i]]);
}
}
}
return dp[n][amount] > amount ? -1 : dp[n][amount];
}
}
|
空间优化：我感觉空间优化还是得先写出二维的之后，从代码的角度进行优化。代码中每次转移是依赖于左下角 dp[i + 1][j - coins[i]] 的，对于依赖左下角和右上角的状态转移方程，我们用正序；依赖右下角或左上角的则用倒序，例如 01 背包。
如果要从完全背包的角度看，那就是每个硬币能取无数次，状态 dp[i + 1][j] 需要转移到仍能取本次硬币的 dp[i + 1][j - coins[i]]，而非到无法取本次硬币的 dp[i][j - coins[i]]，这就是 01 背包的方法了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public int coinChange(int[] coins, int amount) {
int n = coins.length;
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
for (int i = 0; i < n; i++) {
dp[0] = 0;
for (int j = coins[i]; j <= amount; j++) {
dp[j] = Math.min(dp[j], 1 + dp[j - coins[i]]);
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
}
|
这个题和上一题的区别完全只是换了个东西求，之前是求硬币的个数，现在是求方案数，所以说两类边界值的初始化值都变了。对于非法值要初始化为0，因为办不到就是0种方案；对于不取的情况要初始化为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
| class Solution {
public int change(int amount, int[] coins) {
int n = coins.length;
int[][] dp = new int[n + 1][amount + 1];
Arrays.fill(dp[0], 0);
dp[0][0] = 1;
for (int i = 0; i < n; i++) {
dp[i + 1][0] = 1;
for (int j = 1; j <= amount; j++) {
dp[i + 1][j] = dp[i][j];
if (coins[i] <= j) {
dp[i + 1][j] += dp[i + 1][j - coins[i]];
}
}
}
return dp[n][amount];
}
}
class Solution {
public int change(int amount, int[] coins) {
int n = coins.length;
int[] dp = new int[amount + 1];
Arrays.fill(dp, 0);
for (int i = 0; i < n; i++) {
dp[0] = 1;
for (int j = coins[i]; j <= amount; j++) {
dp[j] += dp[j - coins[i]];
}
}
return dp[amount];
}
}
|
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
| class Solution {
public int numSquares(int n) {
int target = n;
n = (int) Math.sqrt(target) + 1;
int[][] dp = new int[n + 1][target + 1];
for (int j = 0; j <= target; j++) {
dp[1][j] = j;
}
for (int i = 2; i <= n; i++) {
for (int j = 0; j <= target; j++) {
dp[i][j] = dp[i - 1][j];
if (i * i <= j) {
dp[i][j] = Math.min(dp[i][j], dp[i][j - i * i] + 1);
}
}
}
return dp[n][target];
}
}
|
空间优化，这种无需额外变量的空间优化只要考虑清楚是正序还是逆序就行。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public int numSquares(int n) {
int target = n;
n = (int) Math.sqrt(target) + 1;
int[] dp = new int[target + 1];
for (int j = 0; j <= target; j++) { dp[j] = j; }
for (int i = 2; i <= n; i++) {
for (int j = i * i; j <= target; j++) {
dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
}
}
return dp[target];
}
}
|
4. 线性DP
4.1 最长公共子序列（LCS）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int longestCommonSubsequence(String text1, String text2) {
char[] c1 = text1.toCharArray(), c2 = text2.toCharArray();
int n = c1.length, m = c2.length;
int[][] dp = new int[n + 1][m + 1];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (c1[i] == c2[j]) {
dp[i + 1][j + 1] = dp[i][j] + 1;
} else {
dp[i + 1][j + 1] = Math.max(dp[i + 1][j], dp[i][j + 1]);
}
}
}
return dp[n][m];
}
}
|
空间优化：需要用到 2 个额外变量来存储即将被覆盖的 dp[j+1]；对比完全背包，其实完全背包只有 i 这一个递推的维度，只需要 i+1 的上一个 dp[i][j]，而这个题还需要 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
| class Solution {
public int longestCommonSubsequence(String text1, String text2) {
char[] c1, c2;
if (text1.length() > text2.length()) {
c1 = text1.toCharArray(); c2 = text2.toCharArray();
} else {
c2 = text1.toCharArray(); c1 = text2.toCharArray();
}
int n = c1.length, m = c2.length;
int[] dp = new int[m + 1];
int upLeft;
for (int i = 0; i < n; i++) {
upLeft = dp[0];
dp[0] = 0;
for (int j = 0; j < m; j++) {
int tmp = dp[j + 1];
if (c1[i] == c2[j]) {
dp[j + 1] = upLeft + 1;
} else {
dp[j + 1] = Math.max(dp[j], dp[j + 1]);
}
upLeft = tmp;
}
}
return dp[m];
}
}
|
非常典的一个题，这里的边界初始化只能用循环，注意n和m都要取等号
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public int minDistance(String word1, String word2) {
char[] w1 = word1.toCharArray(), w2 = word2.toCharArray();
int n = w1.length, m = w2.length;
int[][] dp = new int[n + 1][m + 1];
for (int i = 0; i <= n; i++) { dp[i][0] = i; }
for (int j = 0; j <= m; j++) { dp[0][j] = j; }
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (w1[i] == w2[j]) {
dp[i + 1][j + 1] = dp[i][j];
} else {
dp[i + 1][j + 1] = 1 + Math.min(dp[i][j], Math.min(dp[i + 1][j], dp[i][j + 1]));
}
}
}
return dp[n][m];
}
}
|
空间优化：也是要用到额外的两个变量
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
| class Solution {
public int minDistance(String word1, String word2) {
char[] w1 = word1.toCharArray(), w2 = word2.toCharArray();
int n = w1.length, m = w2.length;
int[] dp = new int[m + 1];
for (int j = 0; j <= m; j++) { dp[j] = j; }
for (int i = 0; i < n; i++) {
int upLeft = dp[0];
dp[0] = i + 1;
for (int j = 0; j < m; j++) {
int tmp = dp[j + 1];
if (w1[i] == w2[j]) {
dp[j + 1] = upLeft;
} else {
dp[j + 1] = 1 + Math.min(upLeft, Math.min(dp[j], dp[j + 1]));
}
upLeft = tmp;
}
}
return dp[m];
}
}
|
和编辑距离没区别，状态转移方程更简单一些。
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
| class Solution {
public int minDistance(String word1, String word2) {
char[] cw1 = word1.toCharArray();
char[] cw2 = word2.toCharArray();
int n1 = cw1.length, n2 = cw2.length;
int[][] dp = new int[n1 + 1][n2 + 1];
for (int i = 0; i <= n1; i++) {
dp[i][0] = i;
}
for (int j = 0; j <= n2; j++) {
dp[0][j] = j;
}
for (int i = 0; i < n1; i++) {
for (int j = 0; j < n2; j++) {
if (cw1[i] == cw2[j]) {
dp[i + 1][j + 1] = dp[i][j];
} else {
dp[i + 1][j + 1] = Math.min(dp[i][j + 1], dp[i + 1][j]) + 1;
}
}
}
return dp[n1][n2];
}
}
|
注意 . 和其他字符的匹配情况都被封装在 match 函数之中了，以及带 * 的可以匹配空字符，分 p[j] 为 * 和不为 * 两种情况考虑。比较难的是等于 * 的情况，分匹配零次和匹配多次考虑，针对匹配多次的情况，递归到 s 的前一个位置。
这里用的是 0-based 算法，或许对于本题而言，1-based 更适合，下次重写的话就用 1-based。
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
| class Solution {
public boolean isMatch(String s, String p) {
char[] sc = s.toCharArray(), pc = p.toCharArray();
int n = sc.length, m = pc.length;
boolean[][] dp = new boolean[n + 1][m + 1];
dp[0][0] = true;
for (int j = 1; j < m; j++) {
if (pc[j] == '*') {
dp[0][j + 1] = dp[0][j - 1];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (pc[j] == '*') {
dp[i + 1][j + 1] |= dp[i + 1][j - 1];
if (!dp[i + 1][j + 1] && match(sc[i], pc[j - 1])) {
dp[i + 1][j + 1] |= dp[i][j + 1];
}
} else {
if (match(sc[i], pc[j])) {
dp[i + 1][j + 1] = dp[i][j];
} else {
dp[i + 1][j + 1] = false;
}
}
}
}
return dp[n][m];
}
boolean match(char a, char b) {
if (b == '.') {
return true;
}
return a == b;
}
}
|
4.2 最长递增子序列（LIS）
这个题有两种做法，前者直接使用动态规划，复杂度为 O(n^2)，后者贪心+二分，可以将时间复杂度优化到 O(nlogn)
方法一：直接 DP，还是非常容易理解的，用 dp[i] 表示以 nums[i] 结尾的最长递增子序列，然后取 dp[] 中最大的元素，
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public int lengthOfLIS(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
Arrays.fill(dp, 1);
int ans = 1;
for (int i = 1; i < n; i++) {
int max = 0;
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
max = Math.max(dp[j], max);
}
}
dp[i] = max + 1;
ans = Math.max(ans, dp[i]);
}
return ans;
}
|
方法二：贪心+二分，用 dp[i] 记录长度为 i 的 IS 的最小末尾值
注意Arrays.binarySearch的特性，它并不是找第一个大于等于num的元素，而仅仅是寻找等于；如果找不到等于的，就会返回负数。但是这个返回的负数取补码后的值，标记了第一个大于num的元素的位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length, len = 0;
int[] dp = new int[n];
for (int i = 0; i < n; i++) {
int j = Arrays.binarySearch(dp, 0, len, nums[i]);
if (j < 0) { j = ~j; }
dp[j] = nums[i];
if (j == len) { len++; }
}
return len;
}
}
|
这是 2026-01-31 的双周赛，思想就是 LIS，但强制要用 O(nlogn) 算法，因为数据量比较大，注意 Integer 自带的一些处于二进制的函数，例如 .toBinaryString() 是将一个数转化为二进制字符串。具体见我的周赛博客。
5. 划分DP
5.1 判定能否划分
一般定义 f[i] 表示长为 i 的前缀 a[:i] 能否划分，在进行状态转移时，枚举 i 左边的端点，例如左端点为 L，判断 a[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
| class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
int n = s.length();
int maxLength = 0;
for (String word : wordDict) {
maxLength = Math.max(maxLength, word.length());
}
Set<String> wordSet = new HashSet<>(wordDict);
boolean[] dp = new boolean[n + 1];
Arrays.fill(dp, false);
dp[0] = true;
for (int i = 0; i < n; i++) {
for (int j = i; j >= Math.max(0, i - maxLength + 1); j--) {
String subWord = s.substring(j, i + 1);
if (dp[j - 1 + 1] && wordSet.contains(subWord)) {
dp[i + 1] = true;
break;
}
}
}
return dp[n];
}
}
|
6. 状态机DP
122. 买卖股票的最佳时机 II
7. 其他线性DP
7.1 一维DP
发生在前缀/后缀之间的转移，例如从 f[i−1] 转移到 f[i]，或者从 f[j] 转移到 f[i]
入门比较难的题，此处采用 0-based 方法，即 for 循环的下标是 [0,n)，每轮循环算的是 dp[i + 1]，而 sc[i] 则直接用下标 i 表示。
dp[i+1] 表示以 sc[i] 结尾的括号字符串的最长有效括号长度，在 sc[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
| class Solution {
public int longestValidParentheses(String s) {
char[] sc = s.toCharArray();
int n = sc.length;
if (n <= 1) {
return 0;
}
int ans = 0;
int[] dp = new int[n + 1];
dp[0] = 0; dp[1] = 0;
for (int i = 1; i < n; i++) {
if (sc[i] == '(') {
dp[i + 1] = 0;
} else {
if (sc[i - 1] == '(') {
dp[i + 1] = dp[i - 1] + 2;
} else {
if (i - dp[i] - 1 >= 0 && sc[i - dp[i] - 1] == '(') {
dp[i + 1] = dp[i] + 2 + dp[i - dp[i] - 1];
}
}
}
ans = Math.max(ans, dp[i + 1]);
}
return ans;
}
}
|
专题训练
跳跃游戏
第一问：
第二问：
第三问：
