参考刷题指南

labuladong动态规划系列

动态规划答疑

子序列

子序列问题解题模板

参考labuladong教程：子序列解题模板

思路1：一个一维的 dp 数组

在子数组array[0..i]中，以array[i]结尾的目标子序列的长度是dp[i]。

思路2：一个二维的 dp 数组

思路2.1：涉及两个字符串/数组时

在子数组arr1[0..i]和子数组arr2[0..j]中，我们要求的子序列长度为dp[i][j]。

思路2.2：只涉及一个字符串/数组时

在子数组array[i..j]中，我们要求的子序列（最长回文子序列）的长度为dp[i][j]。

300. 最长递增子序列

参考labuladong教程：从最长递增子序列学会如何推状态转移方程

**dp[i]**： 表示以 nums[i] 这个数结尾的最长递增子序列的长度。

base case：所有dp[i]的 初始值均为 1，因为以 nums[i] 结尾的最长递增子序列起码要包含它自己。

状态转移关系：nums[i] = x，既然是递增子序列，我们只要找到前面那些结尾比 x 小的子序列，然后把 x 接到最后，就可以形成一个新的递增子序列，而且这个新的子序列长度加一。因此对i之前的dp[j]遍历一遍，若num[j]小于x的话就读取对应的dp[j]加1，然后与当前dp[i]比较，取最大值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);

        for (int i = 0; i < nums.length; i++){
            for (int j = 0; j < i; j++){
                if (nums[i] > nums[j]) dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }

        int res = 0;
        for (int k = 0; k < dp.length; k++){
            res = Math.max(res, dp[k]);
        }

        return res;
    }
}

正常人想不出来的基于patience game纸牌玩法加上二分搜索的方法：

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 lengthOfLIS(int[] nums) {
        int[] top = new int[nums.length];

        int cards = 0;
        for (int i = 0; i < nums.length; i++){
            int poker = nums[i];

            int left = 0, right = cards;
            while (left < right){
                int mid = (left + right) / 2;
                if (poker < top[mid]) right = mid;
                else if (poker > top[mid]) left = mid + 1;
                else right = mid;
            }

            if (left == cards) cards++;

            top[left] = poker;
        }

        return cards;
    }
}

知识点：子序列和子串的区别

  • 子串一定是连续的
  • 子序列不一定是连续的

646. 最长数对链

与300题相比需要先对数对进行排序，因为本题可以以任何顺序选择其中的一些数对来构造。

**dp[i]**： 表示以 pairs[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
class Solution {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, new Comparator<int[]>(){
            public int compare(int[] a, int[] b){
                if (a[0] == b[0]) return a[1] - b[1];
                else return a[0] - b[0];
            }
        });

        int[] dp = new int[pairs.length];
        Arrays.fill(dp, 1);

        for (int i = 0; i < pairs.length; i++){
            for (int j = 0; j < i; j++){
                if (pairs[i][0] > pairs[j][1]) dp[i] = Math.max(dp[i], dp[j]+1);
            }
        }

        int res = 0;
        for (int k = 0; k < pairs.length; k++){
            res = Math.max(res, dp[k]);
        }

        return res;
    }
}

知识点：lambda表达式实现Comparator的重写

参考：Comparator接口实现排序

376. 摆动序列

**dp[i]**： dp[i][0]表示以 nums[i] 这个数结尾的最长摆动序列的长度，dp[i][1]表示以 nums[i] 这个数结尾的最长摆动序列的最后一个差值的正负性，分别用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
28
class Solution {
    public int wiggleMaxLength(int[] nums) {
        int[][] dp = new int[nums.length][2];
        for (int[] a : dp) Arrays.fill(a, 1);

        for (int i = 0; i < nums.length; i++){
            for (int j = 0; j < i; j++){
                if (nums[i] == nums[j]) continue;

                if (j == 0){ //对于跟在nums[0]后面、长度为2的序列默认进行初始化
                    dp[i][1] = nums[i] -nums[j] > 0 ? 1 : -1;
                    dp[i][0] = 2;
                }
                else if ((nums[i] - nums[j]) * dp[j][1] < 0 && dp[j][0] + 1 > dp[i][0]){
                    dp[i][0] = dp[j][0] + 1;
                    dp[i][1] = nums[i] - nums[j] > 0 ? 1 : -1;
                }
            }
        }

        int res = 0;
        for (int k = 0; k < dp.length; k++){
            res = Math.max(res, dp[k][0]);
        }

        return res;
    }
}

智商碾压的解法：

**两个dp**：假设up[i]表示 nums[0:i] 中最后两个数字是递增的最长摆动序列长度，down[i] 表示 nums[0:i] 中最后两个数字是递减的最长摆动序列长度，只有一个数字时默认为 1。

状态转移关系：

当nums[i+1] > nums[i]：
假设 down[i] 表示的最长摆动序列的最远末尾元素下标正好为 i，遇到新的上升元素后，up[i+1] = down[i] + 1 ，这是因为 up 一定从 down 中产生（初始除外），并且 down[i] 此时最大。
假设 down[i] 表示的最长摆动序列的最远末尾元素下标小于i，设为 j，那么 nums[j:i] 一定是递增的。（因为若完全递减，最远元素下标等于 i；若波动，那么 down[i] > down[j]。均不符合假设。）由于 nums[j:i] 递增，down[j:i] 一直等于 down[j] ，依然满足 up[i+1] = down[i] + 1 。

当nums[i+1] < nums[i]时同理。

由于 down 和 up 只和前一个状态有关，所以可以优化存储，分别用一个变量即可。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int wiggleMaxLength(int[] nums) {
        int up = 1, down = 1;
        for (int i = 1; i < nums.length; i++){
            if (nums[i] > nums[i-1]) up = down + 1;
            else if (nums[i] < nums[i-1]) down = up + 1;
        }

        return nums.length == 0 ? 0 : Math.max(up, down);
    }
}

354. 俄罗斯套娃信封问题

参考labuladong教程：信封嵌套问题

解法：先对宽度 w 进行升序排序，如果遇到 w 相同的情况，则按照高度 h 降序排序。之后把所有的 h 作为一个数组，在这个数组上计算 LIS 的长度就是答案。

这个解法的关键在于，对于宽度 w 相同的数对，要对其高度 h 进行降序排序。因为两个宽度相同的信封不能相互包含的，逆序排序保证在 w 相同的数对中最多只选取一个。

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
class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, new Comparator<int[]>(){
            public int compare(int[] a, int[] b){
                if (a[0] == b[0]) return b[1] - a[1];
                else return a[0] - b[0];
            }
        });

        int[] heigth = new int[envelopes.length];
        for (int i = 0; i < envelopes.length; i++){
            heigth[i] = envelopes[i][1];
        }

        return lengthOfLIS(heigth);

    }

    int lengthOfLIS(int[] nums){
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);

        for (int i = 0; i < nums.length; i++){
            for (int j = 0; j < i; j++){
                if (nums[i] > nums[j]) dp[i] = Math.max(dp[j]+1, dp[i]);
            }
        }

        int res = 0;
        for (int k = 0; k < dp.length; k++){
            res = Math.max(res, dp[k]);
        }

        return res;
    }
}

知识点：Arrays.sort重写Comparator接口实现二维数组排序

参考：

53. 最大子序和（子数组）

参考labuladong教程：经典动态规划：最大子数组和

**dp[i]**：以 nums[i] 为结尾的「最大子数组和」。

base case：dp[0] = nums[0];

状态转移关系：dp[i] 有两种「选择」，要么与前面的相邻子数组连接，形成一个和更大的子数组；要么不与前面的子数组连接，自成一派，自己作为一个子数组。既然要求「最大子数组和」，当然选择结果更大的那个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int maxSubArray(int[] nums) {
        if (nums.length == 0) return 0;

        int[] dp = new int[nums.length];
        dp[0] = nums[0];

        for (int i = 1; i < nums.length; i++){
            dp[i] = Math.max(nums[i], nums[i] + dp[i-1]);
        }

        int res = Integer.MIN_VALUE;
        for (int j = 0; j < dp.length; j++){
            res = Math.max(res, dp[j]);
        }

        return res;
    }
}

dp[i] 仅仅和 dp[i-1] 的状态有关，可以把dp数组状态压缩成两个不断更新的值：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int maxSubArray(int[] nums) {
        if (nums.length == 0) return 0;

        int dp_1 = 0, dp_0 = nums[0], res = dp_0;

        for (int i = 1; i < nums.length; i++){
            dp_1 = Math.max(nums[i], nums[i] + dp_0);
            dp_0 = dp_1;
            res = Math.max(res, dp_1);
        }

        return res;
    }
}

1143. 最长公共子序列

参考labuladong教程：详解最长公共子序列问题，秒杀三道动态规划题目

**dp[i][j]**：对于s1[0...i-1]和s2[0...j-1]，它们的最长公共子序列长度。

base case：专门让索引为0的行和列表示空串，dp[0][...]和dp[...][0]均初始化为0。

状态转移关系：

如果s1[i] == s2[j]，说明这个字符一定在lcs中，那么就能在 s1 的前 i-1 个字符与 s2 的前 j-1 个字符最长公共子序列的基础上再加上 s1[i]/s2[j] 这个值，最长公共子序列长度加 1，从dp[i-1][j-1]加上1就是dp[i][j]的长度。

如果s1[i] != s2[j]意味着，s1[i]和s2[j]中至少有一个字符不在lcs中，此时最长公共子序列为 s1 的前i-1 个字符和 s2 的前 j 个字符最长公共子序列，或者 s1 的前 i 个字符和 s2 的前 j-1 个字符最长公共子序列，取它们的最大者，即从dp[i][j-1]和dp[i-1][j]中选出较大的那个lcs保存下来继续往后更新。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int[][] dp = new int[text1.length() + 1][text2.length() + 1];
        for (int[] a : dp) Arrays.fill(a, 0);

        for (int i = 1; i <= text1.length(); i++){
            for (int j = 1; j <= text2.length(); j++){
                if (text1.charAt(i-1) == text2.charAt(j-1)) dp[i][j] = dp[i-1][j-1] + 1;
                else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }

        return dp[text1.length()][text2.length()];
    }
}

状态压缩：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int[] dp = new int[text2.length() + 1];

        for (int i = 1; i <= text1.length(); i++){
            int pre = 0;
            for (int j = 1; j <= text2.length(); j++){
                int temp = dp[j];
                if (text1.charAt(i-1) == text2.charAt(j-1)) dp[j] = pre + 1;
                else dp[j] = Math.max(dp[j], dp[j-1]);
                pre = temp;
            }
        }

        return dp[text2.length()];
    }
}

知识点：String基操

LIS与LCS的不同

与最长递增子序列相比，最长公共子序列有以下不同点：

  • 针对的是两个序列，求它们的最长公共子序列。
  • 在最长递增子序列中，dp[i] 表示以 s[i] 为结尾的最长递增子序列长度，子序列必须包含 s[i] ；在最长公共子序列中，dp[i][j] 表示 s1 中前 i 个字符与 s2 中前 j 个字符的最长公共子序列长度，不一定包含 s1[i] 和 s2[j]。
  • 在求最终解时，最长公共子序列中 dp[N][M] 就是最终解，而最长递增子序列中 dp[N] 不是最终解，因为以 s[N] 为结尾的最长递增子序列不一定是整个序列最长递增子序列，需要遍历一遍 dp 数组找到最大者。

583. 两个字符串的删除操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int minDistance(String word1, String word2) {
        int[][] dp = new int[word1.length()+1][word2.length()+1];
        for (int[] a : dp) Arrays.fill(a, 0);

        for (int i = 1; i <= word1.length(); i++){
            for (int j = 1; j <= word2.length(); j++){
                if (word1.charAt(i-1) == word2.charAt(j-1)) dp[i][j] = dp[i-1][j-1] + 1;
                else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }

        int LCS = dp[word1.length()][word2.length()];

        return word1.length() - LCS + word2.length() - LCS;
    }
}

状态压缩：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int minDistance(String word1, String word2) {
        int[] dp = new int[word2.length()+1];

        for (int i = 1; i <= word1.length(); i++){
            int pre = 0;
            for (int j = 1; j <= word2.length(); j++){
                int temp = dp[j];
                if (word1.charAt(i-1) == word2.charAt(j-1)) dp[j] = pre + 1;
                else dp[j] = Math.max(dp[j], dp[j-1]);
                pre = temp;
            }
        }

        int LCS = dp[word2.length()];

        return word1.length() - LCS + word2.length() - LCS;
    }
}

712. 两个字符串的最小ASCII删除和

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 minimumDeleteSum(String s1, String s2) {
        int[][] dp = new int[s1.length() + 1][s2.length() + 1];

        for (int i = 1; i <= s1.length(); i++){
            for (int j = 1; j <= s2.length(); j++){
                if (s1.charAt(i-1) == s2.charAt(j-1)) dp[i][j] = dp[i-1][j-1] + (int)(s1.charAt(i-1)); //char值强制转换为int就是它的ASCII码值
                else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }

        int LCSASCII = dp[s1.length()][s2.length()];

        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        int sum1 = 0, sum2 = 0;

        for (int i : c1) sum1 += i;
        for (int j : c2) sum2 += j;

        return sum1 - LCSASCII + sum2 - LCSASCII;
    }
}

状态压缩：

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 minimumDeleteSum(String s1, String s2) {
        int[] dp = new int[s2.length() + 1];

        for (int i = 1; i <= s1.length(); i++){
            int pre = 0;
            for (int j = 1; j <= s2.length(); j++){
                int temp = dp[j];
                if (s1.charAt(i-1) == s2.charAt(j-1)) dp[j] = pre + (int)(s1.charAt(i-1));
                else dp[j] = Math.max(dp[j], dp[j-1]);
                pre = temp;
            }
        }

        int LCSASCII = dp[s2.length()];

        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        int sum1 = 0, sum2 = 0;

        for (int i : c1) sum1 += i;
        for (int j : c2) sum2 += j;

        return sum1 - LCSASCII + sum2 - LCSASCII;
    }
}

72. 编辑距离

参考labuladong教程：编辑距离

**dp[i][j]**：dp[i-1][j-1]存储 s1[0..i] 和 s2[0..j] 的最小编辑距离。

base case： i 走完 s1 或 j 走完 s2，可以直接返回另一个字符串剩下的长度。

状态转移关系：对于每对字符 s1[i] 和 s2[j]，可以有四种操作：

1
2
3
4
5
6
7
8
if s1[i] == s2[j]:
    啥都别做（skip）
    i, j 同时向前移动
else:
    三选一：#全试一遍，选值最小的
        插入（insert）
        删除（delete）
        替换（replace）

具体关系：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int minDistance(String word1, String word2) {
        int[][] dp = new int[word1.length()+1][word2.length()+1];

        for (int i = 1; i <= word1.length(); i++) dp[i][0] = i;
        for (int j = 1; j <= word2.length(); j++) dp[0][j] = j;

        for (int i = 1; i <= word1.length(); i++){
            for (int j = 1; j <= word2.length(); j++){
                if (word1.charAt(i-1) == word2.charAt(j-1)) dp[i][j] = dp[i-1][j-1];
                else dp[i][j] = minThree(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1;
            }
        }

        return dp[word1.length()][word2.length()];
    }

    int minThree(int a, int b, int c){
        return Math.min(a, Math.min(b, c));
    }
}

状态压缩（仅压缩成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
class Solution {
    public int minDistance(String word1, String word2) {
        if (word1.isEmpty()) return word2.length();
        if (word2.isEmpty()) return word1.length();

        int[][] dp = new int[2][word2.length()+1];

        dp[1][0] = 1;
        for (int j = 1; j <= word2.length(); j++) dp[0][j] = j;

        for (int i = 1; i <= word1.length(); i++){
            for (int j = 1; j <= word2.length(); j++){
                if (word1.charAt(i-1) == word2.charAt(j-1)) dp[1][j] = dp[0][j-1];
                else dp[1][j] = minThree(dp[0][j], dp[1][j-1], dp[0][j-1]) + 1;
            }
            for(int k = 0; k < word2.length() + 1; k++) dp[0][k] = dp[1][k];
            dp[1][0] = i+1;
        }

        return dp[1][word2.length()];
    }

    int minThree(int a, int b, int c){
        return Math.min(a, Math.min(b, c));
    }
}

516. 最长回文子序列

参考labuladong教程：子序列解题模板：最长回文子序列

**dp[i][j] **：在子串s[i..j]中，最长回文子序列的长度为dp[i][j]。

base case：如果只有一个字符，显然最长回文子序列长度是 1，也就是dp[i][j] = 1,(i == j)。因为i肯定小于等于j，所以对于那些i > j的位置，根本不存在什么子序列，应该初始化为 0。

状态转移关系：取决于s[i]和s[j]的字符：

如果它俩相等，那么它俩加上s[i+1..j-1]中的最长回文子序列就是s[i..j]的最长回文子序列（+2）；

如果它俩不相等，说明它俩不可能同时出现在s[i..j]的最长回文子序列中，那么把它俩分别加入s[i+1..j-1]中，看看哪个子串产生的回文子序列更长即可，即取原来的最大值而不增加回文串的长度。

具体关系：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];

        for (int i = 0; i < n; i++) dp[i][i] = 1;

        for (int i = n - 2; i >= 0; i--){
            for (int j = i + 1; j < n; j++){
                if (s.charAt(i) == s.charAt(j)) dp[i][j] = dp[i+1][j-1] + 2;
                else dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
            }
        }

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

注：遍历方向是按列从下往上，按行从左往右

状态压缩，dp数组从二维降到一维，参考labuladong教程：

压缩后的一维 dp 数组：就是之前二维 dp 数组的 dp[i][..] 那一行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[] dp = new int[n];
        Arrays.fill(dp, 1);

        for (int i = n - 2; i >= 0; i--){
            int pre = 0; // 存储 dp[i+1][j-1] 的变量
            for (int j = i + 1; j < n; j++){
                int temp = dp[j];
                if (s.charAt(i) == s.charAt(j)) dp[j] = pre + 2;
                else dp[j] = Math.max(dp[j], dp[j-1]);
                pre = temp; // 到下一轮循环，pre 就是 dp[i+1][j-1] 了，因为j++了
            }
        }

        return dp[n-1];
    }
}

else dp[j] = Math.max(dp[j], dp[j-1]);解析：在对 dp[j] 赋新值之前，dp[j] 的值就是外层 for 循环上一次迭代算出来的值，也就是对应二维 dp 数组中 dp[i+1][j] 的位置。dp[j-1] 的值就是内层 for 循环上一次迭代算出来的值，也就是对应二维 dp 数组中 dp[i][j-1] 的位置。

temp和pre解析：dp[i+1][j-1] 会被 dp[i][j-1] 覆盖掉，即一维数组里当前循环里的dp[j-1]（上一轮循环里的dp[j]，因此要在上一轮里先保存dp[j]）。

1312. 让字符串成为回文串的最少插入次数

参考labuladong教程：构造回文的最小插入次数

**dp[i][j] **：对字符串 s[i..j]，最少需要进行 dp[i][j] 次插入才能变成回文串。

base case：当 i == j 时 dp[i][j] = 0，因为当 i == j 时 s[i..j] 就是一个字符，本身就是回文串，所以不需要进行任何插入操作。

状态转移关系：通过 dp[i+1][j-1] 推导 dp[i][j]，取决于s[i]和s[j]的字符：

如果它俩相等，不需要进行任何插入，只要知道如何把 s[i+1..j-1] 变成回文串即可。

如果它俩不相等，首先是做选择，先将 s[i..j-1] 或者 s[i+1..j] 变成回文串，谁变成回文串的插入次数少就选谁（即Math.min()）。然后根据前面的选择，将 s[i..j] 变成回文，至少进行一次插入，即+1。

具体关系：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int minInsertions(String s) {
        int[][] dp = new int[s.length()][s.length()];

        for (int i = s.length() - 2; i >= 0; i--){
            for (int j = i + 1; j < s.length(); j++){
                if (s.charAt(i) == s.charAt(j)) dp[i][j] = dp[i+1][j-1];
                else dp[i][j] = Math.min(dp[i+1][j], dp[i][j-1]) + 1;
            }
        }

        return dp[0][s.length()-1];
    }
}

状态压缩：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int minInsertions(String s) {
        int[] dp = new int[s.length()];

        for (int i = s.length() - 2; i >= 0; i--){
            int pre = 0;
            for (int j = i + 1; j < s.length(); j++){
                int temp = dp[j];
                if (s.charAt(i) == s.charAt(j)) dp[j] = pre;
                else dp[j] = Math.min(dp[j], dp[j-1]) + 1;
                pre = temp;
            }
        }

        return dp[s.length()-1];
    }
}

背包问题

0-1背包问题

参考labuladong教程：经典动态规划：0-1 背包问题

**dp[i][w]**：对于前i个物品，当前背包的容量为w，这种情况下可以装的最大价值是dp[i][w]。

base case：dp[0][..] = dp[..][0] = 0，因为没有物品或者背包没有空间的时候，能装的最大价值就是 0。

状态转移关系：

如果没有把这第i个物品装入背包：最大价值dp[i][w]应该等于dp[i-1][w]，不装就是继承之前的结果。

如果把这第i个物品装入了背包：dp[i][w]应该等于dp[i-1][w-wt[i-1]] + val[i-1]。（由于i是从 1 开始的，所以对val和wt的取值是i-1）在装第i个物品的前提下，应该寻求剩余重量w-wt[i-1]限制下能装的最大价值，加上第i个物品的价值val[i-1]，这就是装第i个物品的前提下，背包可以装的最大价值。

1
2
3
4
5
6
7
8
9
10
11
int knapsack(int W, int N, int[] wt, int[] val{
    int[][] dp = new int[N+1][W+1];
    
    for (int i = 1; i <= N; i++){
        for (int w = 1; w <= W; w++){
            if (w - wt[i-1] < 0) dp[i][w] = dp[i-1][w]; //当前背包容量装不下，只能选择不装入背包
            else dp[i][w] = Math.max(dp[i-1][w], dp[i-1][w-wt[i-1]] + val[i-1]); //装入或者不装入背包，择优
        }
    }
    return dp[N][W];
}

416. 分割等和子集

参考labuladong教程：背包问题变体之子集分割

对集合求和，得出 sum，把问题转化为背包问题：给一个可装载重量为 sum / 2 的背包和 N 个物品，每个物品的重量为 nums[i]。现在让你装物品，是否存在一种装法，能够恰好将背包装满？

**dp[i][w] = x**：对于前 i 个物品，当前背包的容量为 j 时，若 x 为 true，则说明可以恰好将背包装满，若 x 为 false，则说明不能恰好将背包装满。

base case：dp[..][0] = true ，因为背包没有空间的时候，就相当于装满了； dp[0][..] = false，当没有物品可选择的时候，肯定没办法装满背包。

状态转移关系：

如果不把 nums[i] 算入子集，或者说不把这第 i 个物品装入背包，那么是否能够恰好装满背包，取决于上一个状态 dp[i-1][j]，继承之前的结果。

如果把 nums[i] 算入子集，或者说把这第 i 个物品装入了背包，那么是否能够恰好装满背包，取决于状态 dp[i-1][j-nums[i-1]]。（由于 i 是从 1 开始的，而数组索引是从 0 开始的，所以第 i 个物品的重量应该是 nums[i-1]）对于dp[i - 1][j-nums[i-1]] ：如果装了第 i 个物品，就要看背包的剩余重量 j - nums[i-1] 限制下是否能够被恰好装满。换句话说，如果 j - nums[i-1] 的重量可以被恰好装满，那么只要把第 i 个物品装进去，也可恰好装满 j 的重量；否则的话，重量 j 肯定是装不满的。

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 boolean canPartition(int[] nums) {
        int sum = 0;
        for (int a : nums) sum += a;
        if (sum % 2 != 0) return false; // 和为奇数时，不可能划分成两个和相等的集合

        int sumHalf = sum / 2;

        boolean[][] dp = new boolean[nums.length + 1][sumHalf + 1];

        // base case, boolean默认值为false
        for (int i = 0; i <= nums.length; i++) dp[i][0] = true; 

        for (int i = 1; i <= nums.length; i++){
            for (int j = 1; j <= sumHalf; j++){
                if (j - nums[i - 1] < 0) dp[i][j] = dp[i-1][j]; // 背包容量不足，不能装入第 i 个物品
                else dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]]; // 装入或不装入背包
            }
        }

        return dp[nums.length][sumHalf];
    }
}

322. 零钱兑换

参考labuladong教程：动态规划详解

**dp[i]**：当目标金额为 i 时，至少需要 dp[i] 枚硬币凑出。

base case：dp[0] = 0 ，目标金额 amount 为 0 时算法返回 0，因为不需要任何硬币就已经凑出目标金额了。

状态转移关系：

如果把 nums[i] 算入子集，或者说把这第 i 个物品装入了背包，那么是否能够恰好装满背包，取决于状态 dp[i-1][j-nums[i-1]]。（由于 i 是从 1 开始的，而数组索引是从 0 开始的，所以第 i 个物品的重量应该是 nums[i-1]）对于dp[i - 1][j-nums[i-1]] ：如果装了第 i 个物品，就要看背包的剩余重量 j - nums[i-1] 限制下是否能够被恰好装满。换句话说，如果 j - nums[i-1] 的重量可以被恰好装满，那么只要把第 i 个物品装进去，也可恰好装满 j 的重量；否则的话，重量 j 肯定是装不满的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];

        // 数组大小为 amount + 1，初始值也为 amount + 1，因为如果可以凑齐的话硬币数量肯定会小于amount+1， 用于最后检验是否能够凑齐
        for (int i = 0; i <= amount; i++) dp[i] = amount + 1; 
        dp[0] = 0; //base case

        for (int j = 1; j <= amount; j++){ // 外层 for 循环在遍历所有状态的所有取值
            for (int coin : coins){ // 内层 for 循环在求所有选择的最小值
                if (j - coin < 0) continue; // 子问题无解，跳过
                else dp[j] = Math.min(dp[j], dp[j-coin] + 1); //+1意为加上当前这块硬币
            }
        }

        if (dp[amount] == amount + 1) return -1;
        else return dp[amount];
    }
}

518. 零钱兑换 II

参考labuladong教程：背包问题之零钱兑换

问题转化：有一个背包，最大容量为 amount，有一系列物品 coins，每个物品的重量为 coins[i]，每个物品的数量无限。请问有多少种方法，能够把背包恰好装满？状态有两个，就是「背包的容量」和「可选择的物品」。

**dp[i][j]**：若只使用前 i 个物品，当背包容量为 j 时，有 dp[i][j] 种方法可以装满背包。翻译回本题的意思：若只使用 coins 中的前 i 个硬币的面值，若想凑出金额 j，有 dp[i][j] 种凑法。

base case： dp[0][..] = 0，如果不使用任何硬币面值，就无法凑出任何金额。dp[..][0] = 1，如果凑出的目标金额为 0，那么“无为而治”就是唯一的一种凑法。

状态转移关系：

如果不把这第 i 个物品装入背包：也就是说不使用 coins[i] 这个面值的硬币，那么凑出面额 j 的方法数 dp[i][j] 应该等于 dp[i-1][j]，继承之前的结果。

如果把这第 i 个物品装入了背包，也就是说使用 coins[i] 这个面值的硬币，那么 dp[i][j] 应该等于 dp[i][j-coins[i-1]]。（ i 是从 1 开始的，所以 coins 的索引是 i-1 时表示第 i 个硬币的面值）对于dp[i][j-coins[i-1]]：如果决定使用这个面值的硬币，那么就应该关注如何凑出金额 j - coins[i-1]。

想求的 dp[i][j] 是「共有多少种凑法」，所以 dp[i][j] 的值应该是以上两种选择的结果之和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int change(int amount, int[] coins) {
        int[][] dp = new int[coins.length + 1][amount + 1];

        for (int i = 0; i <= coins.length; i++) dp[i][0] = 1;

        for (int i = 1; i <= coins.length; i++){
            for (int j = 1; j <= amount; j++){
                if (j - coins[i-1] < 0) dp[i][j] = dp[i-1][j];
                else dp[i][j] = dp[i-1][j] + dp[i][j - coins[i-1]];
            }
        }

        return dp[coins.length][amount];
    }
}

打家劫舍问题

参考labuladong教程：经典动态规划：打家劫舍系列问题

198. 打家劫舍

dp[i] = x **： 从第i间房子出来**（不包括第i间）开始抢劫，最多能抢到的钱为x。

base case：dp[n] = 0，走过了最后一间房子后，就没得抢了，能抢到的钱显然是 0。

状态转移关系：看注释

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int rob(int[] nums) {
        int[] dp = new int[nums.length + 2];
        for (int i = nums.length - 1; i >= 0; i--){
            dp[i] = Math.max(dp[i+1], //不抢，去下家
                             nums[i] + dp[i+2]); // 抢，带上第i+1家的钱（nums数组里下标是i）去下下家
        }

        return dp[0];
    }
}

状态压缩：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int rob(int[] nums) {
        int dp_1 = 0, dp_2 = 0;
        int dp = 0;
        
        for (int i = nums.length - 1; i >= 0; i--){
            dp = Math.max(dp_1, nums[i] + dp_2);
            dp_2 = dp_1;
            dp_1 = dp;
        }

        return dp;
    }
}

213. 打家劫舍 II

首尾房间不能同时被抢，那么只可能有三种不同情况：要么都不被抢；要么第一间房子被抢最后一间不抢；要么最后一间房子被抢第一间不抢。但只要比较情况二和情况三就行，因为这两种情况对于房子的选择余地比情况一大。

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 rob(int[] nums) {
        int n = nums.length;
        if (n == 1) return nums[0];
        
        return Math.max(robRange(nums, 0, n-2), robRange(nums, 1, n-1));
    }

    // 仅计算闭区间 [start,end] 的最优结果
    int robRange(int[] nums, int start, int end) {
        int dp_1 = 0, dp_2 = 0;
        int dp = 0;
        
        for (int i = end; i >= start; i--){
            dp = Math.max(dp_1, nums[i] + dp_2);
            dp_2 = dp_1;
            dp_1 = dp;
        }

        return dp;
    }
}

337. 打家劫舍 III

原来的暴力dfs写法：

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
class Solution {
    int max = 0;
    public int rob(TreeNode root) {
        skipDfs(root);
        return max;
    }

    int skipDfs(TreeNode root){
        if (root == null) return 0;
        int[] a = {0,0,0,0};
        int left = 0, right = 0;

        if (root.left != null){
            left = skipDfs(root.left);
            if (root.left.left != null) a[0] = skipDfs(root.left.left);
            if (root.left.right != null) a[1] = skipDfs(root.left.right);
        } 
        
        if (root.right != null){
            right = skipDfs(root.right);
            if (root.right.left != null) a[2] = skipDfs(root.right.left);
            if (root.right.right != null) a[3] = skipDfs(root.right.right);
        }      

        int sub_max = 0;
        for (int num:a){
            sub_max += num;
        }

        max = Math.max(max, sub_max+root.val);
        max = Math.max(max, left+right);

        return Math.max(left + right, sub_max + root.val);

    }
}

加上备忘录的优化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    HashMap<TreeNode, Integer> memo = new HashMap<>();

    public int rob(TreeNode root) {
        if (root == null) return 0;

        if (memo.containsKey(root)) return memo.get(root);

        // 抢，然后去下下家做选择
        int do_it = root.val + (root.left == null ? 0 : rob(root.left.left) + rob(root.left.right)) + (root.right == null ? 0 : rob(root.right.left) + rob(root.right.right));

        // 不抢，然后去下家做选择
        int not_do = rob(root.left) + rob(root.right);

        // 选择收益更大的
        int res = Math.max(not_do, do_it);

        memo.put(root, res);
        return res;
    }
}

股票问题

参考labuladong教程：团灭 LeetCode 股票买卖问题

通用思路框架

穷举框架

利用「状态」进行穷举。具体到每一天，看看总共有几种可能的「状态」，再找出每个「状态」对应的「选择」。穷举的目的是根据对应的「选择」更新状态。具体框架：

1
2
3
4
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 择优(选择1，选择2...)

每天都有三种「选择」：买入、卖出、无操作，用 buy, sell, rest 表示。

「状态」有三个：第一个是天数，第二个是允许交易的最大次数，第三个是当前的持有状态（即之前说的 rest 的状态，不妨用 1 表示持有，0 表示没有持有）

用一个三维数组表示这几种状态的全部组合：

1
2
3
4
5
6
7
8
9
dp[i][k][0 or 1]
0 <= i <= n-1, 1 <= k <= K
n 为天数，大 K 为最多交易数
此问题共 n × K × 2 种状态，全部穷举就能搞定。

for 0 <= i < n:
    for 1 <= k <= K:
        for s in {0, 1}:
            dp[i][k][s] = max(buy, sell, rest)

**dp[i][k][0/1]**：今天是第i天，至今最多进行了k次交易，当前手上未持有/持有股票，最多获得的利润数。

想求的最终答案是 dp[n - 1][K][0]。

状态转移框架

1
2
3
4
5
6
7
8
9
10
11
12
13
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
              max(   选择 rest  ,             选择 sell      )

解释：今天我没有持有股票，有两种可能：
要么是我昨天就没有持有，然后今天选择 rest，所以我今天还是没有持有；
要么是我昨天持有股票，但是今天我 sell 了，所以我今天没有持有股票了。

dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
              max(   选择 rest  ,           选择 buy         )

解释：今天我持有着股票，有两种可能：
要么我昨天就持有着股票，然后今天选择 rest，所以我今天还持有着股票；
要么我昨天本没有持有，但今天我选择 buy，所以今天我就持有股票了。

base case

1
2
3
4
5
6
7
8
dp[-1][k][0] = 0
解释：因为 i 是从 0 开始的，所以 i = -1 意味着还没有开始，这时候的利润当然是 0 。
dp[-1][k][1] = -infinity
解释：还没开始的时候，是不可能持有股票的，用负无穷表示这种不可能。
dp[i][0][0] = 0
解释：因为 k 是从 1 开始的，所以 k = 0 意味着根本不允许交易，这时候利润当然是 0 。
dp[i][0][1] = -infinity
解释：不允许交易的情况下，是不可能持有股票的，用负无穷表示这种不可能。

121. 买卖股票的最佳时机

k = 1。

状态转移方程：

1
2
3
4
5
6
7
8
9
10
dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i])
              max(   选择 rest  ,             选择 sell      )

dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][0] - prices[i])
			= max(dp[i-1][1][1], 0 - price[i])  (k = 0的base case)
              max(   选择 rest  ,           选择 buy         )

可以去掉所有k，变为二维数组 dp[n][0/1] ：
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], -price[i])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;

        int[][] dp = new int[n][2];

        for (int i = 0; i < n; i++){
            if (i - 1 < 0){ //提前解决dp[-1]的问题，先人为取非负无穷的那个作为最大值
                dp[i][0] = 0; // max(0, -infinity + prices[i])
                dp[i][1] = -prices[i]; // max(-infinity, 0 - prices[i])
                continue;
            }

            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i-1][1], -prices[i]);
        }

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

状态压缩：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;

        int dp_0 = 0, dp_1 = Integer.MIN_VALUE;

        for (int i = 0; i < n; i++){
            dp_0 = Math.max(dp_0, dp_1 + prices[i]);
            dp_1 = Math.max(dp_1, -prices[i]);
        }

        return dp_0;
    }
}

122. 买卖股票的最佳时机 II

k = +infinity，可以认为 k 和 k - 1 是一样的。可以这样改写框架：

1
2
3
4
5
6
7
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
            = max(dp[i-1][k][1], dp[i-1][k][0] - prices[i])

数组中的 k 已经不会改变了，也就是说不需要记录 k 这个状态了：
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]) （除了这里的dp[i-1][0]之外都和 k = 1 一个样）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;

        int[][] dp = new int[n][2];

        for (int i = 0; i < n; i++){
            if (i - 1 < 0){ //提前解决dp[-1]的问题，先人为取非负无穷的那个作为最大值
                dp[i][0] = 0; // max(0, -infinity + prices[i])
                dp[i][1] = -prices[i]; // max(-infinity, 0 - prices[i])
                continue;
            }

            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);
        }

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

状态压缩：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;

        int dp_0 = 0, dp_1 = Integer.MIN_VALUE;

        for (int i = 0; i < n; i++){
            int temp = dp_0; //由于下面dp_1需要用到上一轮的dp_0，先存着
            dp_0 = Math.max(dp_0, dp_1 + prices[i]);
            dp_1 = Math.max(dp_1, temp - prices[i]); 
        }

        return dp_0;
    }
}

309. 最佳买卖股票时机含冷冻期

k = +infinity

每次 sell 之后要等一天才能继续交易。只要把这个特点融入上一题的状态转移方程即可：

1
2
3
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])
解释：第 i 天选择 buy 的时候，要从 i-2 的状态转移，而不是 i-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
class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;

        int[][] dp = new int[n][2];

        for (int i = 0; i < n; i++){
            if (i - 1 < 0){ //提前解决dp[-1]的问题，先人为取非负无穷的那个作为最大值
                dp[i][0] = 0; // max(0, -infinity + prices[i])
                dp[i][1] = -prices[i]; // max(-infinity, 0 - prices[i])
                continue;
            }

            if (i - 2 < 0){ //提前解决dp[-1]的问题，这里直接人为给dp[-1][0]赋值
                dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
                dp[i][1] = Math.max(dp[i-1][1], -prices[i]);
                continue;
            }

            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i-1][1], dp[i-2][0] - prices[i]);
        }

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

状态压缩：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;

        int dp_0 = 0, dp_1 = Integer.MIN_VALUE;
        int dp_0_pre = 0;

        for (int i = 0; i < n; i++){
            int temp = dp_0;
            dp_0 = Math.max(dp_0, dp_1 + prices[i]);
            dp_1 = Math.max(dp_1, dp_0_pre - prices[i]);
            dp_0_pre = temp; //传到下一轮时，dp_0_pre就是i-2，dp_0就是i-1 
        }

        return dp_0;
    }
}

714. 买卖股票的最佳时机含手续费

k = +infinity

每次交易要支付手续费，只要把手续费从利润中减去即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;

        int[][] dp = new int[n][2];

        for (int i = 0; i < n; i++){
            if (i - 1 < 0){
                dp[i][0] = 0;
                dp[i][1] = -prices[i] - fee;
                continue;
            }

            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i] - fee);
        }

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

状态压缩：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;

        int dp_0 = 0, dp_1 = Integer.MIN_VALUE;

        for (int i = 0; i < n; i++){
            int temp = dp_0;
            dp_0 = Math.max(dp_0, dp_1 + prices[i]);
            dp_1 = Math.max(dp_1, temp - prices[i] - fee); 
        }

        return dp_0;
    }
}

123. 买卖股票的最佳时机 III

k = 2

1
2
3
原始的动态转移方程，没有可化简的地方
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])

对于k的穷举：for (int k = max_k; k >= 1; k--)，max_k就是题目给定的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
class Solution {
    public int maxProfit(int[] prices) {
        int max_k = 2;
        int n = prices.length;

        int[][][] dp = new int[n][max_k+1][2];

        for (int i = 0; i < n; i++){
            for (int j = 1; j <= max_k; j++){
                if (i - 1 < 0){
                    dp[i][j][0] = 0;
                    dp[i][j][1] = -prices[i];
                    continue;
                }

                dp[i][j][0] = Math.max(dp[i-1][j][0], dp[i-1][j][1] + prices[i]);
                dp[i][j][1] = Math.max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i]);
            }
        }

        return dp[n-1][max_k][0];

    }
}

穷举k=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
class Solution {
    public int maxProfit(int[] prices) {
        int max_k = 2;
        int n = prices.length;

        int[][][] dp = new int[n][max_k+1][2];

        for (int i = 0; i < n; i++){
            if (i - 1 < 0){
                dp[i][1][0] = 0;
                dp[i][1][1] = -prices[i];
                dp[i][2][0] = 0;
                dp[i][2][1] = -prices[i];// 这里也要穷举k=1和2的情况
                continue;
            }
            //穷举k=1/2
            dp[i][1][0] = Math.max(dp[i-1][1][0], dp[i-1][1][1] + prices[i]);
            dp[i][1][1] = Math.max(dp[i-1][1][1], dp[i-1][0][0] - prices[i]); //这里的k=0 base case是0，但数组初始化都是0就不用管
            dp[i][2][0] = Math.max(dp[i-1][2][0], dp[i-1][2][1] + prices[i]);
            dp[i][2][1] = Math.max(dp[i-1][2][1], dp[i-1][1][0] - prices[i]);
        }

        return dp[n-1][max_k][0];

    }
}

状态压缩：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;

        int dp_10 = 0, dp_11 = Integer.MIN_VALUE;
        int dp_20 = 0, dp_21 = Integer.MIN_VALUE;

        for (int i = 0; i < n; i++){
            dp_10 = Math.max(dp_10, dp_11 + prices[i]);
            dp_11 = Math.max(dp_11, -prices[i]);
            dp_20 = Math.max(dp_20, dp_21 + prices[i]);
            dp_21 = Math.max(dp_21, dp_10 - prices[i]);
        }

        return dp_20;

    }
}

188. 买卖股票的最佳时机 IV

最通用的k和n来了：

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 maxProfit(int k, int[] prices) {
        int n = prices.length;
        if (n == 0) return 0;

        int[][][] dp = new int[n][k+1][2];

        for (int i = 0; i < n; i++){
            for (int j = 1; j <= k; j++){
                if (i - 1 < 0){
                    dp[i][j][0] = 0;
                    dp[i][j][1] = -prices[i];
                    continue;
                }

                dp[i][j][0] = Math.max(dp[i-1][j][0], dp[i-1][j][1] + prices[i]);
                dp[i][j][1] = Math.max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i]);
            }
        }

        return dp[n-1][k][0];
    }
}

内存优化：一次交易由买入和卖出构成，至少需要两天。所以说有效的限制 k 应该不超过 n/2，如果超过，就没有约束作用了，相当于 k = +infinity。这种情况是之前解决过的。因此加一个判断：

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 maxProfit(int k, int[] prices) {
        int n = prices.length;
        if (n == 0) return 0;
        if (k > n/2) return maxProfit_infi(prices);

        int[][][] dp = new int[n][k+1][2];

        for (int i = 0; i < n; i++){
            for (int j = 1; j <= k; j++){
                if (i - 1 < 0){
                    dp[i][j][0] = 0;
                    dp[i][j][1] = -prices[i];
                    continue;
                }

                dp[i][j][0] = Math.max(dp[i-1][j][0], dp[i-1][j][1] + prices[i]);
                dp[i][j][1] = Math.max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i]);
            }
        }

        return dp[n-1][k][0];
    }

    int maxProfit_infi(int[] prices) {
        int n = prices.length;

        int dp_0 = 0, dp_1 = Integer.MIN_VALUE;

        for (int i = 0; i < n; i++){
            int temp = dp_0;
            dp_0 = Math.max(dp_0, dp_1 + prices[i]);
            dp_1 = Math.max(dp_1, temp - prices[i]); 
        }

        return dp_0;
    }
}

其他经典问题

10. 正则表达式匹配

参考labuladong教程：动态规划之正则表达式

**dp(s, i, p, j) **：返回值为boolean型的dp函数，若为true，则表示 s[i..]可以匹配p[j..]；若为false，则表示不能匹配。

base case和状态转移关系参照代码注释：

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
class Solution {
    HashMap<String, Boolean> memo = new HashMap<>();

    public boolean isMatch(String s, String p) {    
        return dp(s, 0, p, 0);
    }

    boolean dp(String s, int i, String p, int j){
        int m = s.length(), n = p.length();

        //base case
        //当p被匹配完了，需要s也要恰好匹配完才算成功
        if (j == n) return i == m;

        //当s被匹配完了，p恰好匹配完是一种成功的情况
        //也有一种情况是p后面全是通配符，全部匹配0次（匹配上一个空串）也算成功（.只能匹配单字符，不算空串）
        if (i == m){
            //如果能匹配空串，一定是字符和通配符成对出现，长度为偶数
            if ((n - j) % 2 == 1) return false;

            //检验是不是一个字符搭配一个通配符，要完全符合这种形式才行
            for (; j + 1 < n; j+=2)
                if (p.charAt(j + 1) != '*') return false;

            return true; 
        }

        //memo记录重叠子问题
        String key = Integer.toString(i) + ',' + Integer.toString(j);
        if (memo.containsKey(key)) return memo.get(key);

        boolean res = false;

        
        if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.'){ //匹配
            if (j < n - 1 && p.charAt(j + 1) == '*') res = dp(s, i, p, j+2) || dp(s, i+1, p, j); //有通配符的情况，有可能匹配0次或多次，j+2意为匹配0次，跳过了这个字符跟后面的通配符；i+1表示匹配多次，先迈进一步，继续往后匹配
            else res = dp(s, i+1, p, j+1); //无通配符，常规匹配一次
        }
        else{ //不匹配
            if (j < n - 1 && p.charAt(j + 1) == '*') res = dp(s, i, p, j+2); //有通配符，只能匹配0次，饶你一命
            else res = false; //无通配符，直接GG
        }

        memo.put(key, res);//录入备忘录

        return res;
    }
}

651. 4键键盘

参考labuladong教程：动态规划之四键键盘

**dp[i] **： i 次操作后最多能显示多少个 A。

最优按键序列一定只有两种情况：

要么一直按 A：A,A,…A（当 N 比较小时）。

要么是这么一个形式：A,A,…C-A,C-C,C-V,C-V,…C-V（当 N 比较大时）。

因此只需比较最后一步是哪种操作令A更多即可。

base case和状态转移关系参照代码注释：

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 maxA(int N) {
        int[] dp = new int[N + 1];
        dp[0] = 0;

        for(int i = 1; i <= N; i++){
            // 按 A 键，就比上次多一个 A 而已
            dp[i] = dp[i - 1] + 1;
            
            
            for (int j = 2; j < i; j++){
                // 从第2步操作开始遍历（第一次肯定要按一个A键），找到进入复制粘贴模式的最佳时机
                // 全选 & 复制 dp[j-2]，连续粘贴 i - j 次
            	// 屏幕上共 dp[j - 2] * (i - j + 1) 个 A
                // 如果比单按一个 A 或者是更早进入复制粘贴模式更多的话就更新dp[i]
                dp[i] = Math.max(dp[i], dp[j - 2] * (i - j + 1));
            }
        }

        return dp[N];
    }
}

650. 只有两个键的键盘

**dp[i] **： 能显示 i 个 A的最小操作次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int minSteps(int n) {
        if (n == 1) return 0;
        int[] dp = new int[n+1];

        for (int i = 2; i <= n; i++){
            dp[i] = i;
            for (int j = 2; j * j <= n; j++){
                if (i % j == 0) {
                    dp[i] = Math.min(dp[i], dp[j] + dp[i/j]);
                    break;// 事实证明每个因数对的dp[i]都是相等的，只有1*i不一样
                }
            }
        }

        return dp[n];
    }
}

变成数学找因数的方法，完爆动规：

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 minSteps(int n) {
        if (n == 1) return 0;
        if (isPrime(n)) return n;

        int min = Integer.MAX_VALUE;

        for (int i = 2; i*i <= n; i++){
            if (n % i == 0){
                int j = n / i;
                int res = Math.min(minSteps(i) + j, minSteps(j) + i);
                min = Math.min(res, min);
            }
        }

        return min;
    }

    boolean isPrime(int n){
        if (n < 2) return false;
        if (n == 2) return true;
        if (n % 2 == 0) return false;

        for (int i = 3; i*i <= n; i+=2){
            if (n % i == 0) return false;
        }

        return true;
    }
}

887. 鸡蛋掉落

参考labuladong教程：经典动态规划：高楼扔鸡蛋

**dp(k, n) **：K 个鸡蛋，面对 N 层楼时的最坏情况下的最小测试次数。

base case：当楼层数N等于 0 时，显然不需要扔鸡蛋；当鸡蛋数K为 1 时，显然只能线性扫描所有楼层。

状态转移关系：如果鸡蛋碎了，那么鸡蛋的个数K应该减一，搜索的楼层区间应该从[1..N]变为[1..i-1]共i-1层楼；如果鸡蛋没碎，那么鸡蛋的个数K不变，搜索的楼层区间应该从 [1..N]变为[i+1..N]共N-i层楼。要求的是最坏情况下扔鸡蛋的次数，所以鸡蛋在第i层楼碎没碎，取决于哪种情况的结果更大（我们在写代码时无法知道到底会不会碎）。而需要最少扔鸡蛋次数，则需要把这个最坏情况跟之前已有的结果取最小值。

就算加上memo也会超出时间限制的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
class Solution {
    HashMap<String, Integer> memo = new HashMap<>();

    public int superEggDrop(int k, int n) {
        return dp(k, n);
    }
    
    int dp(int k, int n){
        if (k == 1) return n;
        if (n == 0) return 0;

        String key = Integer.toString(k) + ',' + Integer.toString(n);
        if (memo.containsKey(key)) return memo.get(key);

        int res = Integer.MAX_VALUE;
        for (int i = 1; i < n + 1; i++){ //遍历楼层是在做选择，选择在哪一层楼扔这个鸡蛋可以获得接下来的最少操作次数
            res = Math.min(res, Math.max(dp(k - 1, i - 1), dp(k, n - i)) + 1);
        }

        memo.put(key, res);

        return res;
    }
}

参考教程用二分搜索优化遍历楼层过程：

根据单调递增的性质，把dp看成是关于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
40
class Solution {
    HashMap<String, Integer> memo = new HashMap<>();

    public int superEggDrop(int k, int n) {
        return dp(k, n);
    }
    
    int dp(int k, int n){
        if (k == 1) return n;
        if (n == 0) return 0;

        String key = Integer.toString(k) + ',' + Integer.toString(n);
        if (memo.containsKey(key)) return memo.get(key);

        int res = Integer.MAX_VALUE;
        
        //for (int i = 1; i < n + 1; i++){
            //res = Math.min(res, Math.max(dp(k - 1, i - 1), dp(k, n - i)) + 1);
        //}

        int low = 1, high = n;
        while (low <= high){
            int mid = (low + high) / 2; //让i值从中点开始寻找，mid即为原来for循环的i值
            int broken = dp(k - 1, mid - 1), unbroken = dp(k, n - mid);

            if (broken > unbroken){ //mid处在山谷右边，区间缩右边界
                high = mid - 1;
                res = Math.min(res, broken + 1);
            }
            else { //mid处在山谷左边，区间缩左边界
                low = mid + 1;
                res = Math.min(res, unbroken + 1);
            }
        }

        memo.put(key, res);

        return res;
    }
}

重新定义状态转移关系，更优化的方法：

原来：

1
2
3
dp[k][n] = m
# 当前状态为 k 个鸡蛋，面对 n 层楼
# 这个状态下最少的扔鸡蛋次数为 m

现在：

1
2
3
dp[k][m] = n
# 当前有 k 个鸡蛋，可以尝试扔 m 次鸡蛋
# 这个状态下，最坏情况下最多能确切测试一栋 n 层的楼

base case：dp[0][..] = 0，dp[..][0] = 0

状态转移关系：

1
dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1

dp[k][m - 1] 就是楼上的楼层数，因为鸡蛋个数 k 不变，也就是鸡蛋没碎，还能扔的鸡蛋次数 m 减一；

dp[k - 1][m - 1] 就是楼下的楼层数，因为鸡蛋个数 k 减一，也就是鸡蛋碎了，同时还能扔的鸡蛋次数 m 减一。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int superEggDrop(int k, int n) {
        // m 最多不会超过 N 次（线性扫描）,所以尽可能初始化为n列
        int[][] dp = new int[k+1][n+1];

        int m = 0;
        while (dp[k][m] < n){ //循环结束的条件是 dp[K][m] == N，也就是给你 K 个鸡蛋，测试 m 次，最坏情况下最多能测试 N 层楼
            m++;
            
            for (int i = 1; i <= k; i++) dp[i][m] = dp[i][m-1] + dp[i-1][m-1] + 1;
        }
        //要求的不是 dp 数组里的值，而是某个符合条件的索引 m，所以用 while 循环来找到这个 m 而已

        return m;
    }
}

​

312. 戳气球

参考labuladong教程：经典动态规划：戳气球问题

问题转化：nums[-1] = nums[n] = 1，那么先直接把这两个边界加进去，形成一个新的数组points。其中气球的索引变成了从1到n，points[0] = 1和points[n+1] = 1可以认为是两个「虚拟气球」。

**dp[i][j] = x**：戳破气球i和气球j之间（开区间，不包括i和j）的所有气球，可以获得的最高分数为x。

base case：dp[i][j] = 0，其中0 <= i <= n+1, j <= i+1，因为这种情况下，开区间(i, j)中间根本没有气球可以戳。

状态转移关系：气球i和气球j之间的所有气球都可能是最后被戳破的那一个，不防假设为k。如果最后一个戳破气球k，dp[i][j]的值应该为：

1
2
dp[i][j] = dp[i][k] + dp[k][j] 
         + points[i]*points[k]*points[j]

要最后戳破气球k，得先把开区间(i, k)的气球都戳破，再把开区间(k, j)的气球都戳破；最后剩下的气球k，相邻的就是气球i和气球j，这时候戳破k的话得到的分数就是points[i]*points[k]*points[j]。戳破开区间(i, k)和开区间(k, j)的气球最多能得到的分数就是dp[i][k]和dp[k][j]。对于一组给定的i和j，只要遍历i < k < j的所有气球k，选择得分最高的作为dp[i][j]的值即可.

关于「状态」的穷举，最重要的一点就是：状态转移所依赖的状态必须被提前计算出来。

遍历方向：根据 base case 和最终状态进行推导。

dp[i][j]所依赖的状态是dp[i][k]和dp[k][j]，那么我们必须保证：在计算dp[i][j]时，dp[i][k]和dp[k][j]已经被计算出来了（其中i < k < j）。如下图所示，我们需要i从下到上、j从左到右遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int maxCoins(int[] nums) {
        int sz = nums.length;
        int[] points = new int[sz + 2];

        points[0] = 1;
        points[sz + 1] = 1;

        for (int i = 1; i <= sz; i++) points[i] = nums[i - 1];

        int[][] dp = new int[sz + 2][sz + 2];

        for (int i = sz; i >= 0; i--){
            for (int j = i + 1; j < sz + 2; j++){
                for (int k = i + 1; k < j; k++) dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k][j] + points[k] * points[i] * points[j]);
            }
        }

        return dp[0][sz+1];
    }
}

494. 目标和

参考labuladong教程：回溯算法和动态规划，谁是谁爹？

回溯

框架：

1
2
3
4
5
6
7
8
9
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

实现：

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 {
    int result = 0;

    public int findTargetSumWays(int[] nums, int S) {
        if (nums.length == 0) return 0;
        backtrack(nums, S, 0);
        return result;
    }

    void backtrack(int[] nums, int S, int start){
        // base case
        if (start == nums.length){
            if (S == 0) result++; // 说明恰好凑出 S
            return;
        }

        // 给 nums[i] 选择 - 号
        S += nums[start];
        backtrack(nums, S, start + 1); // 穷举 nums[i + 1]
        S -= nums[start]; // 撤销选择

        // 给 nums[i] 选择 + 号
        S -= nums[start];
        backtrack(nums, S, start + 1); // 穷举 nums[i + 1]
        S += nums[start]; // 撤销选择
    }
}

消除重叠子问题

一般是用 Python 的元组配合哈希表 dict 来做备忘录的，其他语言没有元组，可以用把「状态」转化为字符串作为哈希表的键，这是一个常用的小技巧。

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 findTargetSumWays(int[] nums, int S) {
        if (nums.length == 0) return 0;

        return dp(nums, S, 0);
    }

    HashMap<String, Integer> memo = new HashMap<>();

    int dp(int[] nums, int S, int start){
        if (start == nums.length){
            if (S == 0) return 1;
            return 0;
        }

        String key = S + "," + start;

        if (memo.containsKey(key)) return memo.get(key);

        int result = dp(nums, S - nums[start], start + 1) + dp(nums, S + nums[start], start + 1);

        memo.put(key, result);

        return result;
    }
}

动态规划

把 nums 划分成两个子集 A 和 B，分别代表分配 + 的数和分配 - 的数，那么他们和 target 存在如下关系：

1
2
3
4
sum(A) - sum(B) = target
sum(A) = target + sum(B)
sum(A) + sum(A) = target + sum(B) + sum(A)
2 * sum(A) = target + sum(nums)

综上，可以推出 sum(A) = (target + sum(nums)) / 2。

原问题转化成：nums 中存在几个子集 A，使得 A 中元素的和为 (target + sum(nums)) / 2？

变成背包问题的标准形式：有一个背包，容量为 sum，现在给你 N 个物品，第 i 个物品的重量为 nums[i - 1]（注意 1 <= i <= N），每个物品只有一个，请问你有几种不同的方法能够恰好装满这个背包？

**dp[i][j] = x**：若只在前 i 个物品中选择，若当前背包的容量为 j，则最多有 x 种方法可以恰好装满背包。（若只在 nums 的前 i 个元素中选择，若目标和为 j，则最多有 x 种方法划分子集。）

base case：dp[0][..] = 0，因为没有物品的话，根本没办法装背包；dp[..][0] = 1，因为如果背包的最大载重为 0，「什么都不装」就是唯一的一种装法。

状态转移关系：

如果不把 nums[i] 算入子集，或者说不把这第 i 个物品装入背包，那么恰好装满背包的方法数就取决于上一个状态 dp[i-1][j]，继承之前的结果。

如果把 nums[i] 算入子集，或者说把这第 i 个物品装入了背包，那么只要看前 i - 1 个物品有几种方法可以装满 j - nums[i-1] 的重量就行了，所以取决于状态 dp[i-1][j-nums[i-1]]。

PS：注意我们说的 i 是从 1 开始算的，而数组 nums 的索引时从 0 开始算的，所以 nums[i-1] 代表的是第 i 个物品的重量，j - nums[i-1] 就是背包装入物品 i 之后还剩下的容量。

由于 dp[i][j] 为装满背包的总方法数，所以应该以上两种选择的结果求和，得到状态转移方程：

1
dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-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
class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        int sum = 0;
        for (int num : nums) sum += num;

        if (sum < S || (sum + S) % 2 != 0) return 0; // 这两种情况，不可能存在合法的子集划分

        S = (sum + S) / 2;

        int n = nums.length;
        int[][] dp = new int[n+1][S+1];

        for (int i = 0; i <= n; i++) dp[i][0] = 1;

        for (int i = 1; i <= n; i++){
            for (int j = 0; j <= S; j++){
                if (j >= nums[i-1]) dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]]; // 两种选择的结果之和
                else dp[i][j] = dp[i-1][j]; // 背包的空间不足，只能选择不装物品 i
            }
        }

        return dp[n][S];
    }
}