题目
在这个问题中，您需要将字符串转换成具有最少操作数的回文。操作说明如下：
在任何位置添加任何字符
从任何位置删除任何字符
用另一个字符替换任何位置的任何字符
对字符串执行的每个操作都将计入单位成本。你得尽可能地降低这个数字。
例如，要转换“abccda”，如果只允许添加字符，则至少需要两个操作。但是，当您可以选择替换任何字符时，您只能使用一个操作。我们希望你能利用这项功能为你带来好处。
输入
输入文件包含几个测试用例。输入的第一行给出了测试用例的数量T（1）≤T≤10). 然后T个测试用例将跟随，每个测试用例都在一行中。每个测试用例的输入由一个只包含小写字母的字符串组成。您可以放心地假设这个字符串的长度不会超过1000个字符。
输出
对于每组输入，首先打印测试用例号。然后打印将给定字符串转换为回文所需的最小字符数。
样例输入
6
tanbirahmed
shahriarmanzoor
monirulhasan
syedmonowarhossain
sadrulhabibchowdhury
mohammadsajjadhossain
样例输出
Case 1: 5
Case 2: 7
Case 3: 6
Case 4: 8
Case 5: 8
Case 6: 8
?原题链接：字符串到回文
解题思路
dp[i][j]表示将区间 [ i , j ] 修改成回文串的最小花费。
如果a[ i ]==a[ j ] ，那么dp[ i ][ j ]=dp[ i+1 ][ j?1]?
否则，也就是a[ i ]!=a[ j ]，有五种方案：
删除a[ i ] ，有dp[ i ][ j ]=dp[ i+1][ j ]+1；
删除a[ j ] ，有dp[ i ][ j ]=dp[ i ][ j?1 ]+1；
增加一个和a[ j ] 相同的字符a[ i ] ，有dp[ i ] [ j ]=dp[ i+1 ][ j ]+1；
增加一个和a[ i ] 相同的字符a[ j ] ，有dp[ i ] [ j ]=dp[ i ][ j?1 ]+1；
将 a [ i ]修改成a[ j ] 或将a[ j ]修改成a[ i ] ，有dp[ i ][ j ]=dp[ i+1 ][ j?1 ]+1；
可以发现删除和增加操作转移方程一样，因此总共三种转移方式。
代码
#include <bits/stdc++.h>
using namespace std;
#define M 1005
int dp[M][M];
string s;
int main()
{
int t;
cin>>t;
for(int k=1;k<=t;k++)
{
memset(dp,0,sizeof(dp));
cin>>s;
int n=s.size();
for(int len=1;len<n;len++) //左右区间枚举标准格式
for(int i=0,j=len;j<n;j++,i++)
if(s[i]==s[j]) dp[i][j]=dp[i+1][j-1];
else{
dp[i][j]=min(dp[i+1][j]+1,dp[i][j-1]+1);
dp[i][j]=min(dp[i][j],dp[i+1][j-1]+1);
}
printf("Case %d: %d\n",k,dp[0][n-1]);
}
return 0;
}
|