动态规划之回文数组

动态规划之回文数组

/*给定一个长度为n（n <= 1000）的字符串A，求插入最少多少个字符使得它变成一个回文串。*/

#include

#include<string>˙

using namespace std;

intmin(inti,intj)

{

returni<=j?i:j;

}

int main()

{

string n;

intd[100][100]={0};

cin>>n;

intlen=n.length();

/* for(int i=len-1;i>=0;i--)//从后面开始比较

{

for(int j=i;j

{

if(n[i]==n[j])

d[i][j]=d[i+1][j-1];

else 

d[i][j]=min(d[i+1][j],d[i][j-1])+1;

}

}*/

for(intk=1;k<=len-1;k++)//间隔

{

for(inti=0;i+k<=len;i++)

{

intj=i+k;

if(n[i]==n[j])//如果两个字母相等则不用添加字母 

d[i][j]=d[i+1][j-1];

else//如果不相等则有两种情况。1：加在左边。2:加在右边

d[i][j]=min(d[i+1][j],d[i][j-1])+1;//+1表示添加了一个字母

}

}

cout<

return 0;

}