最长回文串（C++）

这题的思路采用动态规划
设计好dp数组的填充顺序既可以解出来，下面以("cbc",3)为案例演示一遍：
设dp[i][j]的值表示字串l(i<=pos<=j)是否是回文串.
1.显然单个字符是回文串，因此dp[i][i] = 1;
2.dp[i][i+1]的值与s[i]==s[j]是否成立有关;
3.dp[i][j]与(dp[i+1][j-1] == 1 && A[i] == A[j])是否成立有关;

1.设置dp[3][3],不用初始化。
(一)
1##
#1#
##1

(二)
10#
#10
##1

(三)
101
#10
##1

每次循环填充一条对角线，完成之后，寻找j-i+1的最大值即得到问题的解。

class Solution {
public:
    int getLongestPalindrome(string A, int n) {
        // write code here
        int dp[n][n], l, i;
        for(l = 0; l < n; l++){
            for(i = 0; i < n - l; i++){
                int j = i + l;
                if(i == j) dp[i][j] = 1;
                else if(j == i + 1 && A[i] == A[j]) dp[i][j] = 1;
                else{
                    if(dp[i+1][j-1] == 1 && A[i] == A[j]) dp[i][j] = 1;
                    else dp[i][j] = 0;
                }
            }
        }
        int ans = 1, temp=0;
        for(int i = 0; i < n; i++){
            for(int j = i; j < n; j++){
               if(dp[i][j] == 1) temp = j - i + 1;
               ans = ans >= temp ? ans : temp;
            }
        }
        return ans;
    }
};