题解 | #最长回文子串# DP做法

Well,这是算法笔记的原题，使用dp方法来做，有点难度，理解了好久，但还是有点马马虎虎

dp[i][j]=1，表示从i到j的子串是回文字符串；dp[i][j]=0，表示从i到j的子串不是回文字符 串

初始化，由小到大进行初始化，从子串长度为2开始~一直到子串长度为A.size()

状态转移方程

当A[i]=A[j]的时候，dp[i][j] = dp[i + 1][j - 1]；当A[i] ！= A[j]的时候，dp[i][j] = 0；

还有dp[i][i] = 1; 当A[i]=A[i + 1]的时候，dp[i][i + 1] =1

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A string字符串 
     * @return int整型
     */
int getLongestPalindrome(string A) {
    int size = A.size(),ans = 1;
    if(size == 1) return size;
    if(size == 2 && A[0] != A[1]) return 1;
    int dp[size][size];
    memset(dp,0,sizeof(dp));
    //边界
    for(int i = 0; i < size; i++) {
        dp[i][i] = 1;
        if(i < size - 1) {
            if(A[i] == A[i + 1]) {
                dp[i][i + 1] = 1;
                ans = 2;//当前回文字符串的长度
            }
        }
    }
    //状态转移方程
    for(int k = 3; k <= size; k++) {//枚举子串长度
        for(int i = 0; i + k - 1 < size; i++) {//枚举子串的起始端点
            int j = i + k - 1;//子串的右端点
            if(A[i] == A[j] && dp[i + 1][j - 1] == 1) {
                dp[i][j] = 1;
                ans = k;//更新回文字符串的长度
            }
        }
    }
    return ans;
}
};