UVA String to Palindrome(10739)

题目大意：

        给定一个字符串，使用替换字符，增加字符和删除字符三种操作使得字符串变成回文，求出最少的操作次数。

 

解题思路：

        动态规划题目，题中的增加字符和删除字符的操作本质上是一样的，可以都理解为增加字符。

        设dp[i][j] 表示字符串第 i 个字符到第 j 个字符是回文所需操作的次数，则假设第 i+1 到 j-1 的字符是回文了，那么第 i 个字符和第 j 个字符就有两种情况，一种是相等，则 dp[i][j] = dp[i+1][j-1]， 即不用操作；另外一种是不相等，那么就得增加一次操作，操作的方式有三种： dp[i+1][j]，dp[i][j-1] 和 dp[i+1][j-1]， 第一种表示在第 i 个字符那里增加一个和 j 相同的字符， 第二种表示在 j-1 那里增加一个和 i 相同的字符， 第三种就是删除该字符，状态回到 dp[i+1][j-1]，所以状态转移方程就是 ：

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

从三种操作中选取最小的一个，然后加 1。

 

代码如下：

#include <iostream>
#include <cstring>
using namespace std;

int dp[1010][1010];
char s[1010];

int main()
{
	int T, len;

	cin>>T;

	for( int k = 1; k <= T; k++ )
	{
		cin>>s;
		len = strlen(s);
		memset( dp, 0, sizeof( dp ) );

		for( int i = len-1; i >= 0; i-- )
		{
			for( int j = i+1; j < len; j++ )
			{
				if( s[i] == s[j] )
					dp[i][j] = dp[i+1][j-1];
				else
				{
					dp[i][j] = min( dp[i+1][j], min(dp[i][j-1], dp[i+1][j-1] ) ) + 1;
				}
			}
		}

		cout<<"Case "<<k<<": "<<dp[0][len-1]<<endl;
	}

	return 0;
}