算法训练营day47 | {647.回文子串, 516.最长回文子序列}

第九章动态规划-part13，动规最后一天！

647. 回文子串

1.1 解题分析

之前做过的子序列题目，在定义dp数组时，题目求什么，我们就如何定义dp数组，但是本题这样定义很难找到递推关系。我们的dp数组要定义成一个二维dp数组，即**布尔类型的dp[i][j]**，表示区间范围[i,j]的子串是否是回文串，如果是，dp[i][j]为true，否则为false。

字符串s = “aaa”
1
2
3
4
5
6
7
a
a
a
aa
aa
aaa
输出6

DP五部曲：

  1. dp数组定义：
    • dp[i][j]表示闭区间[i,j]范围的子串是否是回文串。
  2. 递推公式：
    • if (s[i] == s[j]) 有三种情况：
      • i == j a
      • i j相差1 aa
      • j - i > 1 此时要继续看里面的子串是否为回文串
    • 同时记录回文子串的数量。
  3. 初始化：
    • 全部为false
  4. 遍历顺序：依据递推公式，本题遍历从下到上，从左到右。
  5. 打印dp数组。

1.2 解题小结

  • 打印dp数组发现只有右半边有更新值。
    1
    2
    3
     true   true   true
    false   true   true
    false  false   true
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
class Solution {
    public int countSubstrings(String s) {
        int result = 0;
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (j - i <= 1) {
                        dp[i][j] = true;
                        result++;
                    } else if (dp[i + 1][j - 1] == true) {
                        dp[i][j] = true;
                        result++;
                    }
                }
            }
        }

        for(boolean[] row : dp) {
            for (boolean val : row) {
                System.out.printf("%7b", val);
            }
            System.out.println();
        }

        return result;
    } 
}

516. 最长回文子序列

2.1 解题分析

DP五部曲：

  1. dp数组定义：
    • dp[i][j]表示闭区间[i,j]范围内的最长回文子序列的长度。
  2. 递推公式：
    • if(s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1] + 2
    • else dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
  3. 初始化：
    • dp[i][i] = 1 i和j往中间靠拢
  4. 遍历顺序：依据递推公式，应从下到上，从左到右遍历。
  5. 打印dp数组。

2.2 解题小结

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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 - 1; 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][j - 1], dp[i + 1][j]);
                }
            }
        }
        return dp[0][n - 1];
    }
}

3. 动态规划专题总结

4. 今日收获

  • 一口气补3天，子序列还可以。
  • 学习时长：2.5小时