动态规划好难！题单：https://leetcode.cn/discuss/post/3581838/fen-xiang-gun-ti-dan-dong-tai-gui-hua-ru-007o/
1. 入门DP
1.1. 爬楼梯
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. 背包问题
背包问题不难，难的是边界的考虑。
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
| 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];
}
}
|
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-1-31的双周赛，思想就是LIS，但强制要用O(nlogn)算法，因为数据量比较大，注意Integer自带的一些处于二进制的函数，例如.toBinaryString()是将一个数转化为二进制字符串。具体见我的周赛博客。
5. 划分DP
5.1 判定能否划分
一般定义f[i]表示长为i的前缀a[:i]能否划分，在进行状态转移时，枚举i左边的端点，例如左端点为L，判断a[L:i]的划分是否满足要求。
注意内层循环在进行状态转移时的下标。
