动态规划——回文串最小分割数

时间:2022-06-20 11:10:49

题目:

给定一个字符串str,返回把str全部切成回文子串的最小分割数。


举例:

str="ABA" ,不需要切割,返回0;

str="ACDCDCDAD",最少需要切两次,比如"A","CDCDC","DAD",所以返回2.


解题思路:动态规划  状态定义:  DP[i]:表示子串(0,i)的最小回文切割数,则最优解在DP[s.length-1]中。(0,i)的子串中包括了i+1个字符,最多分割i次。  状态转移定义   1.初始化:当字串str[0]--str[i](包括i位置的字符)是回文时,DP[i] = 0(表示不需要分割);否则,DP[i] = i(表示至多分割i次);   2.对于任意大于1的i,如果str[j]--str[i]( 1<= j <=  i ,即遍历i之前的每个子串)是回文时,DP[i] = min(DP[i], DP[j-1]+1); 
   (注:j不用取0是因为若j == 0,则又表示判断(0,i))。

代码:
#include <string>
#include <vector>
#include <iostream>
#include<algorithm>
using namespace std;

bool IsPalindrome(const char* str, int begin, int last)//判断str[begin]--str[last]是否为回文串
{
int nbegin = begin;
int nlast = last;
while(nbegin<nlast)
{
if (str[nbegin]!=str[nlast])
return false;
nbegin++;
nlast--;
}
return true;
}


int main( )
{
string strIn;
cin>>strIn;
int nlen = strIn.length();
vector<int> vecDP(nlen,0);
for (int i=1;i<nlen;i++)
{
vecDP[i] = IsPalindrome(strIn.c_str(),0,i)?0:i;//初始化,若为回文串则直接为0
for (int j=i;j>0;j--)
{
if (IsPalindrome(strIn.c_str(),j,i))
{
vecDP[i] = min(vecDP[i],vecDP[j-1]+1);//状态转移
}
}
}
cout<<vecDP[nlen-1];//输出结果

return 0;
}