题目链接:点我
题目
题意:
给你一个字符串,问最少能分成几个回文串.
思路:
动态规划,dp[i]表示 1 到 i 最少可以分成几个回文串,则dp[i] = min(dp[i], dp[j] + 1) && judge(j,i) : 表示由 j + 1 到 i 能形成回文串.
代码:
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
27
28
29
30
31
32
33
34
35
| #include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<iostream>
using namespace std;
const int INF = 1e9 + 10;
int dp[1000+10];
char ss[1000+10];
bool judge(int l,int r){
while(l < r){
if(ss[l] != ss[r])
return false;
l++;
r--;
}return true;
}
int main(){
int t;
scanf("%d", &t);
while(t--){
scanf(" %s", ss+1);
int len = strlen(ss+1);
for(int i = 1; i <= len; ++i){
dp[i] = INF;
for(int j = 0; j < i;++j)
if(judge(j+1,i))
dp[i] = min(dp[i], dp[j] + 1);
}printf("%d\n",dp[len]);
}return 0;
}
|