描述
阿福最近对回文串产生了非常浓厚的兴趣。
如果一个字符串从左往右看和从右往左看完全相同的话，那么就认为这个串是一个回文串。例如，“abcaacba”是一个回文串，“abcaaba”则不是一个回文串。
阿福现在强迫症发作，看到什么字符串都想要把它变成回文的。阿福可以通过切割字符串，使得切割完之后得到的子串都是回文的。
现在阿福想知道他最少切割多少次就可以达到目的。例如，对于字符串“abaacca”，最少切割一次，就可以得到“aba”和“acca”这两个回文子串。
输入输入的第一行是一个整数 T (T <= 20) ，表示一共有 T 组数据。
接下来的 T 行，每一行都包含了一个长度不超过的 1000 的字符串，且字符串只包含了小写字母。输出对于每组数据，输出一行。该行包含一个整数，表示阿福最少切割的次数，使得切割完得到的子串都是回文的。
样例输入
3
abaacca
abcd
abcba
样例输出
1
3
0
提示
对于第一组样例，阿福最少切割 1 次，将原串切割为“aba”和“acca”两个回文子串。
对于第二组样例，阿福最少切割 3 次，将原串切割为“a”、“b”、“c”、“d”这四个回文子串。
对于第三组样例，阿福不需要切割，原串本身就是一个回文串。
1 #include <iostream> 2 #include <string.h> 3 #include <algorithm> 4 #include <cstdio> 5 #include <stdlib.h> 6 #include <string> 7 #include <memory> 8 #include <queue> 9 10 using namespace std; 11 12 const int maxn = 1005; 13 char line[maxn]; 14 int leng; 15 int f[maxn];//直到字符x最少需要分几次才能分成全是回文串 16 17 bool isHuiwen(int s, int e) { 18 int l = e - s + 1; 19 bool flag = true; 20 for (int i = s; i < s + (e - s + 1) / 2; i++) { 21 if (line[i] != line[e - (i - s)]) { 22 flag = false; 23 break; 24 } 25 } 26 return flag; 27 } 28 29 void dp() { 30 for (int i = 1; i < leng; i++) 31 for(int j=0;j<=i;j++) 32 { 33 if (isHuiwen(j, i) && j == 0) 34 { 35 f[i] = 0; 36 break; 37 } 38 if (isHuiwen(j, i)) 39 f[i] = min(f[i], f[j - 1] + 1); 40 } 41 printf("%d ", f[leng - 1]); 42 } 43 44 int main() 45 { 46 int t; 47 scanf("%d", &t); 48 while (t--) { 49 cin >> line; 50 leng = strlen(line); 51 for (int i = 1; i < leng; i++) 52 f[i] = i; 53 dp(); 54 } 55 return 0; 56 }
一开始想的是 用 f[x][y] 存从x到y的字符串最少被分几次 TLE了
其实根本用不着
貌似这个思路叫维度压缩
也就是对我一开始的思路进行了维度打击……
解题思路：
用 f[x] 存放从开始直到字符下标为x的字符串最少要分几次进行动态规划
状态转移方程：
f[x]=min(f[x],f[i]+1)
其中， i+1 到 x 为回文串