动态规划之子序列以及子数组类型的问题_划分多个子数组是哪种动态规划

子序列类型的问题

两种思路

• 第一种思路模板是一个一维的 dp 数组：比如最长递增子序列。在这种思路中 dp 数组的定义是：以 nums[i] 结尾的目标子序列（最长递增子序列）的长度是 dp[i]
• 第二种思路模板是一个二维的 dp 数组，在本思路中 dp 数组的含义又分为「只涉及一个字符串/数组」和「涉及两个字符串/数组」两种情况：
  （1）只涉及一个字符串/数组时（比如最长回文子序列），dp 数组的含义为：在 s[i…j] 中，我们要求的子序列（最长回文子序列）的长度为 dp[i][j]
  （2）涉及两个字符串/数组时（比如最长公共子序列），dp 数组的含义为：在 s1 的 [0…i] 和 s2 的 [0…j] 中，我们要求的子序列（最长公共子序列）长度为dp[i][j]

300. 最长递增子序列

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length]; // 以下标 i 为结尾的最长严格递增子序列的长度是 dp[i]
        Arrays.fill(dp, 1);
        for(int i = 1; i < dp.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 i = 0; i < dp.length; i++){
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

516 最长回文子序列

二维 dp 数组：

class Solution {
    public int longestPalindromeSubseq(String s) {
        // 在 s[i...j] 中，最长回文子序列的长度为 dp[i][j]
        int[][] dp = new int[s.length()][s.length()];
        for(int i = s.length() - 1; i >= 0; i--){
            for(int j = i; j < s.length(); j++){
                if(i == j){
                    dp[i][j] = 1;
                }else{
                    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][s.length() - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

一维 dp 数组：

class Solution {
    public int longestPalindromeSubseq(String s) {
        int[] dp = new int[s.length()];
        for(int i = s.length() - 1; i >= 0; i--){
            int pre = 0; // 记录 dp[i+1][j-1] 的值
            for(int j = i; j < s.length(); j++){
                int temp = dp[j];
                if(i == j){
                    dp[j] = 1;
                }else{
                    if(s.charAt(i) == s.charAt(j)){
                        dp[j] = pre + 2;
                    }else{
                        dp[j] = Math.max(dp[j], dp[j - 1]);
                    }
                    pre = temp;
                }
            }
        }
        return dp[s.length() - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

1143. 最长公共子序列

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        int[][] dp = new int[m + 1][n + 1]; // text1 中 [0,i-1] 的字符串和 text2 中 [0,j-1] 的字符串的公共子序列的长度为 dp[i][j]
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; 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[m][n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

354. 俄罗斯套娃信封问题

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];
                }
                return a[0] - b[0];
            }
        });
        // 最长递增子序列
        int[] dp = new int[envelopes.length]; // 以下标 i 为结尾时最多可以有 dp[i] 个信封
        Arrays.fill(dp, 1);
        for(int i = 1; i < dp.length; i++){
            for(int j = 0; j < i; j++){
                if(envelopes[i][0] > envelopes[j][0] && envelopes[i][1] > envelopes[j][1]){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        } 
        int res = 0;
        for(int i = 0; i < dp.length; i++){
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}
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

72. 编辑距离

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1]; // word1 的前 i 个字符变成 word2 的前 j 个字符所需要的最小操作数是 dp[i][j]
        for(int j = 0; j <= n; j++){
            dp[0][j] = j;
        }
        for(int i = 0; i <= m; i++){
            dp[i][0] = i;
        }
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(word1.charAt(i - 1) == word2.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1];
                }else{
                    // 增，删，改
                    dp[i][j] = getMin(dp[i][j - 1] + 1, dp[i - 1][j] + 1, dp[i - 1][j - 1] + 1);
                }
                
            }
        }
        return dp[m][n];
    }
    public int getMin(int a, int b, int c){
        int min = Math.min(a, b);
        return Math.min(min, c);
    }
}
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

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

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m + 1][n + 1]; // 使 word1 的前 i 个字符和 word2 的前 j 个字符相等所需的最小步数
        for(int i = 0; i <= m; i++){
            dp[i][0] = i;
        }
        for(int j = 0; j <= n; j++){
            dp[0][j] = j;
        }
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(word1.charAt(i - 1) == word2.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1];
                }else{
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;
                    // dp[i][j] = Math.min(dp[i - 1][j - 1] + 2, Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
                }
            }
        }
        return dp[m][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

• 删除后的结果其实就是两个字符串的最长公共子序列，因此本题可以转换为：求两个字符串的最长公共子序列。

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

class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        int[][] dp = new int[m + 1][n + 1]; // 使 s1 的前 i 个字符和 s2 的前 j 个字符相等所需删除字符的 ASCII 值的最小和为 dp[i][j]
        for(int i = 1; i <= m; i++){
            dp[i][0] = dp[i - 1][0] + s1.charAt(i - 1);
        }
        for(int j = 1; j <= n; j++){
            dp[0][j] = dp[0][j - 1] + s2.charAt(j - 1);
        }
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(s1.charAt(i - 1) == s2.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1];
                }else{
                    dp[i][j] = Math.min(dp[i - 1][j - 1] + s1.charAt(i - 1) + s2.charAt(j - 1), Math.min(dp[i - 1][j] + s1.charAt(i - 1), dp[i][j - 1] + s2.charAt(j - 1)));
                }
            }
        }
        return dp[m][n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

子数组类型的问题

53. 最大子序和

class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length]; // 以下标 i 结尾的最大子数组和为 dp[i]
        dp[0] = nums[0];
        for(int i = 1; i < dp.length; i++){
            // 要么不与前面的子数组连接，自成一派，自己作为一个子数组
            // 要么与前面的相邻子数组连接，形成一个和更大的子数组
            dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
        }
        int res = Integer.MIN_VALUE;
        for(int i = 0; i < dp.length; i++){
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

718. 最长重复子数组

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int res = 0;
        // nums1 中以下标 i-1 结尾和 nums2 中以下标 j-1 结尾的最长公共子数组的长度
        int[][] dp = new int[nums1.length + 1][nums2.length + 1];
        for(int i = 1; i <= nums1.length; i++){
            for(int j = 1; j <= nums2.length; j++){
                if(nums1[i - 1] == nums2[j - 1]){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else{
                    dp[i][j] = 0;
                }
                res = Math.max(res, dp[i][j]);
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18