PTA 上的一道动态规划问题(链接),自己做的时候完全想不出来好方法,最后只能用暴力做。

代码太丑就不贴了。

来看柳神的解法吧:1040. Longest Symmetric String (25)-PAT甲级真题(动态规划)

分析:dp[i][j] 表示 s[i]s[j]所表示的字串是否是回文字串。只有 0 和 1,递推方程为:

  1. s[i] == s[j] : dp[i][j] = dp[i + 1][j - 1]
  2. s[i] != s[j] : dp[i][j] =0
  3. 边界:dp[i][i] = 1, dp[i][i + 1] = (s[i] == s[i + 1]) ? 1 : 0 因为 i、j 如果从小到大的顺序来枚举的话,无法保证更新 dp[i][j]的时候 dp[i + 1][j - 1]已经被计算过。因此不妨考虑按照字串的长度和子串的初试位置进行枚举,即第一遍将长度为 3 的子串的 dp 的值全部求出,第二遍通过第一遍结果计算出长度为 4 的子串的 dp 的值…这样就可以避免状态无法转移的问题

首先初始化 dp[i][i] = 1, dp[i][i + 1],把长度为 1 和 2 的都初始化好,然后从 L = 3 开始一直到 L <= len 根据动态规划的递归方程来判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
using namespace std;
int dp[1010][1010];
int main() {
string s;
getline(cin, s);
int len = s.length(), ans = 1;
for(int i = 0; i < len; i++) {
dp[i][i] = 1;
if(i < len - 1 && s[i] == s[i+1]) {
dp[i][i+1] = 1;
ans = 2;
}
}
for(int L = 3; L <= len; L++) {
for(int i = 0; i + L - 1 < len; i++) {
int j = i + L -1;
if(s[i] == s[j] && dp[i+1][j-1] == 1) {
dp[i][j] = 1;
ans = L;
}
}
}
printf("%d", ans);
return 0;
}