PAT甲级A1040---动态规划最长回文子串

1040 Longest Symmetric String (25分)

1040

分析：

dp[i][j]表示s[i]至s[j]所表示的子串是否是回文子串，是则为1，不是则为0。

C++：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 1010;
char str[maxn];
int dp[maxn][maxn];

int main() {
    cin.getline(str, maxn);
    int len = strlen(str), res = 1;
    fill(dp[0], dp[0] + maxn * maxn, 0);
    for (int i = 0; i < len; i++) {
        dp[i][i] = 1;
        if (i < len - 1) {
            if (str[i] == str[i + 1]) {
                dp[i][i + 1] = 1;
                res = 2;
            }
        }
    }
    for (int L = 3; L <= len; L++) {
        for (int i = 0; i + L - 1 < len; i++) {
            int j = i + L - 1;
            if (str[i] == str[j] && dp[i + 1][j - 1] == 1) {
                dp[i][j] = 1;
                res = L;
            }
        }
    }
    printf("%d\n", res);
    return 0;
}