分析:
dp[i][j]表示从i到j最少要添加的字符个数
if(a[i]==a[j])
dp[i][j]=dp[i+1][j-1]; //dp等于上一个状态的dp
else
dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1; //取两种划分的最小值
dp[i][j]=dp[i+1][j-1]; //dp等于上一个状态的dp
else
dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1; //取两种划分的最小值
代码及分析如下:
1 //dp[i][j]表示从i到j最少要添加的字符个数 2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 5 #include<string> 6 #include<algorithm> 7 using namespace std; 8 int dp[105][105]; 9 string a; 10 int min(int x,int y) 11 { 12 if(x<=y) 13 return x; 14 else 15 return y; 16 } 17 18 int main() 19 { 20 int t,len,i,j,Case=1; 21 cin>>t; 22 while(t--) 23 { 24 cin>>a; 25 len=a.size(); 26 memset(dp,0,sizeof(dp)); 27 for(i=len-2;i>=0;i--) //注意i从倒数第二个位置开始 28 for(j=i+1;j<=len-1;j++) //j<=len-1而不是j<=len-2 29 { 30 if(a[i]==a[j]) 31 dp[i][j]=dp[i+1][j-1]; //dp等于上一个状态的dp 32 else 33 dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1; //取两种划分的最小值 34 35 } 36 printf("Case %d: %d ",Case++,dp[0][len-1]); 37 } 38 39 return 0; 40 }