LeetCode之动态规划：子序列问题_给定一个数字序列,你需要确定是否存在一个连续的子序列,使得该子序列中奇数位置上

LeetCode之动态规划：子序列问题

300. 最长递增子序列

子序列是指：由数组中不连续，但相互顺序不变的元素组成的序列。

dp数组的定义：dp[n]表示以nums[n]结尾的最长递增子序列

//O(n2)
public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    //dp[n]表示以nums[n]结尾的最长递增子序列
    int[] dp = new int[n];
    //初始化，每个以自己为结尾的递增子序列至少为1
    Arrays.fill(dp, 1);
    int res = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            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

354. 最长递增子序列2

二维递增子序列。

解题步骤：先进行排序，将问题转换为一维的最大递增子序列问题。

dp数组的定义：dp[n]表示以nums[n]结尾的最长递增子序列

public int maxEnvelopes(int[][] envelopes) {
    int n = envelopes.length;
    if (n == 1) {
        return 1;
    }
    //按照信封的第二个参数升序排序，如果第二个参数相等，对第一个参数进行降序排序
    Arrays.sort(envelopes, (o1, o2) -> {
        if (o1[1] == o2[1]) {
            return o2[0] - o1[0];//降序
        }
        return o1[1] - o2[1];//升序
    });
    //转化为一维的单调最长子序列问题
    //dp[n]表示 以排序后的envelopes[n]为结尾 的最长子序列长度
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    int res = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (envelopes[i][0] > envelopes[j][0]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            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

53. 最大子数组和

这不是一个子序和问题，而是一个连续子数组和问题。

【最大子数组和】就和【最长递增子序列】非常类似，dp 数组的定义是【以 nums[i] 为结尾的最大子数组和/最长递增子序列为 dp[i]】。因为只有这样定义才能将 dp[i+1] 和 dp[i] 建立起联系，利用数学归纳法写出状态转移方程。

public int maxSubArray(int[] nums) {
    int n =nums.length;
    if (n == 1) {
        return nums[0];
    }
    //dp[i]表示 以 nums[i] 为结尾的 具有最大和的连续子数组
    int[] dp = new int[n];
    int res = nums[0];
    for (int i = 0; i < n; i++) {
        //basecase
        if (i == 0) {
            dp[i] = nums[0];
            continue;
        }
        dp[i] = Math.max(dp[i - 1] + nums[i], nums[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

1143. 最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

public int longestCommonSubsequence(String text1, String text2) {
    int n = text1.length();
    int m = text2.length();
    //dp[i][j]表示 text1中前i个字符 和 text2中前j个字符 的最长公共子序列
    int[][] dp = new int[n + 1][m + 1];
    //遍历所有状态
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; 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[n][m];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

712. 最长公共子序列2

给定两个字符串s1, s2，找到使两个字符串相等所需删除字符的ASCII值的最小和。

实质上是【最长公共子序列问题】

public int minimumDeleteSum(String s1, String s2) {
    int n = s1.length();
    int m = s2.length();
    //dp[i][j]表示 使s1前i个字符 和 s2前j个字符 相等所需删除字符的ASCII值的最小和。
    int[][] dp = new int[n + 1][m + 1];
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            //basecase
            if (i == 0 && j == 0) {
                continue;
            }
            //s1为空，则s2全删除
            if (i == 0) {
                dp[0][j] = dp[0][j - 1] + s2.charAt(j - 1) - 'a' + 97;
                continue;
            }
            //s2为空，则s1全删除
            if (j == 0) {
                dp[i][0] = dp[i - 1][0] + s1.charAt(i - 1) - 'a' + 97;
                continue;
            }
            //情况1:当前位置的两个元素相同，则无需删除
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            }
            //情况2：当前两个位置的元素不同
            else {
                //选择 使相等 且 所需删除字符的ASCII值的最小和的情况
                int condition1 = dp[i - 1][j] + s1.charAt(i - 1) - 'a' + 97;
                int condition2 = dp[i][j - 1] + s2.charAt(j - 1) - 'a' + 97;
                dp[i][j] = Math.min(condition1, condition2);
            }
        }
    }
    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
27
28
29
30
31
32
33
34
35
36

72. 最长公共子序列3

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。

可以进行插入、删除、替换三种操作。

实质上是【最长公共子序列问题】

public int minDistance(String word1, String word2) {
    int n = word1.length();
    int m = word2.length();
    //dp[i][j]表示 word1的前i个字符 转换到 word2的前j个字符 的最少操作数
    int[][] dp = new int[n + 1][m + 1];
    //遍历所有状态
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            //basecase
            if (i == 0 && j == 0) {
                continue;
            }
            //表示word1是空，需要的转化次数
            if (i == 0) {
                dp[0][j] = j;
                continue;
            }
            //表示word2是空，需要的转化次数
            if (j == 0) {
                dp[i][0] = i;
                continue;
            }

            //情况1:当前位置上的两个字符相等
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            }
            //情况2:当前位置上的两个字符不等
            else {
                //替换 dp[i-1][j-1]+1
                //插入 dp[i][j-1]+1
                //删除 dp[i-1][j]+1
                dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][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
27
28
29
30
31
32
33
34
35
36
37
38

5. 最长回文子串

回文【子串】

public String longestPalindrome(String s) {
    int n = s.length();
    if (n == 1) {
        return s;
    }
    //dp[i][j]表示：以i为开头，j为结尾的子串是否为回文子串
    boolean[][] dp = new boolean[n][n];
    //初始化
    int start = 0;
    int maxLen = 1;
    char[] array = s.toCharArray();
    //遍历所有情况
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            //子串长度等于1
            //basecase
            if(i==j){
                dp[i][j] = true;
                continue;
            }
            //子串长度等于2
            else if (j - i == 1 && array[i] == array[j]) {
                dp[i][j] = true;
            }
            //子串长度大于2
            else if (array[i] == array[j] && dp[i + 1][j - 1] == true){
                dp[i][j] = true;
            }
            if(dp[i][j] == true){
                if (j - i + 1 > maxLen) {
                    start = i;
                    maxLen = j - i + 1;
                }
            }
        }
    }
    return s.substring(start, start + maxLen);
}
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

516. 最长回文子序列

回文【子序列】

public int longestPalindromeSubseq(String s) {
    int n = s.length();
    if (n == 1) {
        return 1;
    }
    //dp[i][j]表示：以i为开头，j为结尾的子串中的最长回文子序列
    int[][] dp = new int[n][n];
    //初始化
    char[] array = s.toCharArray();
    //遍历所有情况
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            //子串长度等于1
            //basecase
            if(i==j){
                dp[i][j] = 1;
                continue;
            }
            //子串长度等于2
            else if (j - i == 1 && array[i] == array[j]) {
                dp[i][j] = 2;
            }
            //子串长度大于2
            else if (array[i] == array[j]){
                dp[i][j] = dp[i + 1][j - 1] + 2;
            }
            else if(array[i] != array[j]){
                dp[i][j] = Math.max(dp[i + 1][j],dp[i][j - 1]);
            }
        }
    }
    return dp[0][n - 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

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

public int minInsertions(String s) {
    int n = s.length();
    //dp[i][j]表示s[i...j]字符串转化成回文串的最小插入次数
    int[][] dp = new int[n][n];
    char[] array = s.toCharArray();
    //遍历所有的状态
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            //basecase
            if (i == j) {
                continue;
            }
            //子串长度等于2
            if (j - i == 1 && array[i] == array[j]) {
                continue;
            }
            //子串长度大于2
            else if (array[i] == array[j]) {
                dp[i][j] = dp[i + 1][j - 1];
            } else {
                dp[i][j] = Math.min(dp[i][j - 1], dp[i + 1][j]) + 1;
            }
        }
    }
    return dp[0][n - 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