题解 | #最长回文子串#

dp[i][j] = dp[i+1][j-1]， dp[i+1][j-1]是回文 dp[i][j] = 0 表示不是回文

dp的基础是长度，需要每层长度遍历

import java.util.*;

public class Solution {
    public int getLongestPalindrome(String A, int n) {
        int maxLen = 1;
        int dp[][] = new int[n+1][n+1];
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }
        for (int i = 0; i < n-1; i++) {
            if (A.charAt(i) == A.charAt(i+1)) {
                dp[i][i+1] = 1;
                maxLen = 2;
            }
        }
        for (int k = 2; k < n; k++) { // 长度2开始计算
            for (int i = 0; i < n - k; i++) {
                int j = i + k;
                if (A.charAt(i) == A.charAt(j) && dp[i+1][j-1] == 1) {
                    dp[i][j] = 1;
                    if (maxLen < k+1) maxLen = k+1;
                }
            }
        }
        return maxLen;
    }
}