最长回文子串

dp[i][j]表示以A[i]为开头A[j]结尾的回文子串长度，如果不是回文，值为0

• i == j显然有dp[i][j] = 1
• 其他情况有如下事实：长度大于2的回文串，去掉首尾后还是回文串
  所以判断一个串是否是回文，除了要看首尾是否相同，还要看去掉首尾后的子串是否回文，这就是状态从子串转移到母串的规律

这样一来就可以从长度为2的子串入手，一步步提升子串判断长度，将状态转移到整个串。

import java.util.*;

public class Solution {
    public int getLongestPalindrome(String A, int n) {
        int[][] dp = new int[n][n];
        int max = 0;
        for (int i = 0; i < n; ++i) {
            dp[i][i] = 1;
        }
        char[] a = A.toCharArray();
        // 从长度为2的子串入手，一步步提升子串判断长度
        for (int len = 2; len <= n; ++len) {
            // 遍历开头
            for (int i = 0; i <= n - len; ++i) {
                // 子串的结尾
                int j = i + len - 1;
                // 长度大于2的回文串，去掉首尾后还是回文串
                if(a[i] == a[j] && (len == 2 || dp[i + 1][j - 1] != 0)) {
                    dp[i][j] = len;
                    // 因为判断的子串长度递增，答案的值肯定也是非降序更新的，所以不需要比较大小
                    max = len;
                }
            }
        }
        return max;
    }
}