题目描述
小T送给了小L了一串项链。为了方便，我们把项链上形态不同钻石用不同的字母表示。这样小L的项链就变成了一个字符串。
小L忽然想把这串项链优美地切割一下，她想把它切割成尽量少的
回文项链，啊也就是回文串。求最少的切割次数。
输入
第一行一个整数T 表示数据组数
下面T组数据，每一组数据:
只有一行，一个只有小写英文字母的字符串，字符串长度 <= 1000。
输出
对于每一组数据，输出将这个字符串能切割成最少的回文串所需切割的次数。
样例输入 Copy
2
abaacca
abcd
样例输出 Copy
1
3
感觉没思路的题目应该就是动态规划
#include<iostream>
#include<vector>
using namespace std;
bool IsPalindRome(string str){//回文判断
int end=str.length()-;
int start=;
while(start<end){
if(str[start]==str[end]){
start++;
end--;
}else{
return false;
}
}
return true;
}
int minCut(string s) {
int len=s.length();
vector<int> dp(len,);//初始化为0
for(int i=;i<len;i++){
dp[i]=IsPalindRome(s.substr(,i+)) ? : i;//初始化
if(dp[i]==)
continue;
else{
for(int j=;j<=i;j++){
if(IsPalindRome(s.substr(j,i-j+)))
dp[i]=min(dp[i],dp[j-]+);
else{
dp[i]=min(dp[i],dp[j-]+i-j+);
}
}
}
}
return dp[len-];
} int main(){
string str;
int n;
cin>>n;
while(n--){
cin>>str;
cout<<minCut(str)<<endl;
}
}
难点是下面的OK：
int minCut(string s) {
int len=s.length();
vector<int> dp(len,);//初始化为0
for(int i=;i<len;i++){
dp[i]=IsPalindRome(s.substr(,i+)) ? : i;//判断每一步
if(dp[i]==)
continue;
else{
for(int j=;j<=i;j++){
if(IsPalindRome(s.substr(j,i-j+))) //1--i判断回文串
dp[i]=min(dp[i],dp[j-]+);//可以理解
else{
dp[i]=min(dp[i],dp[j-]+i-j+);//可以理解有点难度
}
}
}
}
return dp[len-];
}