题解 | #密码截取# DP

DP

问题转化：本质上是让我们求 “最长连续回文子串”

思路

• dp[i][j] 表示子串 是否为回文子串
• 状态转移方程
  • 若子串 首尾字符相等，即 s[i] == s[j]
    • 当子串长度 == 1 时，表示只有一个字符，一定是回文串
    • 当子串长度 == 2 时，两个字符且首尾相等，也是回文串
    • 否则，即子串长度 > 2 时，则需要判断去掉首尾字符是否为回文串，即判断 dp[i + 1][j - 1]
  • 若子串 首尾字符不相等，即 s[i] != s[j]，则一定不是回文串，即 dp[i][j] = false;
• 顺序：由递推公式可知，从下向上、从左到右

import java.util.*;

// 求最长连续回文子串
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        int n = s.length();
        int res = 1;
        // dp[i][j]表示 s[i, j] 是否为回文子串
        boolean[][] dp = new boolean[n][n];
        // 初始化
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }

        // 顺序：从下向上、从左到右
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                // 递推公式
                if (s.charAt(i) == s.charAt(j)) {
                    // 首尾相等时，则判断去掉首尾字符是否为回文串
                    if (j - i + 1 <= 2) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                } else {
                    dp[i][j] = false;
                }
                if (dp[i][j]) {
                    res = Math.max(j - i + 1, res);
                }
            }
        }
        System.out.println(res);
        in.close();
    }
}