UVa 10739 String to Palindrome (DP)

10739 - String to Palindrome

Time limit: 3.000 seconds 

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=114&page=show_problem&problem=1680

思路：对于每个区间[i, j]：

若str[i] == str[j]，dp[i][j] = dp[i + 1][j - 1];

若str[i] != str[j]， dp[i][j] = min(dp[i + 1][j], dp[i] [j - 1], dp[i + 1] [j - 1]) + 1 （删去i，删去j，修改i为j(添加与删除是一样的)）

完整代码：

/*0.045s*/

#include<bits/stdc++.h>
using namespace std;
const int N = 1005;

int dp[N][N];
char str[N];

int main()
{
	int cas, t = 0, len,i;
	scanf("%d\n", &cas);
	while (cas--)
	{
		gets(str);
		len = strlen(str);
		memset(dp, 0, sizeof(dp));
		for (i = len - 2; i >= 0; --i)
		{
			for (int j = i + 1; j < len; ++j)
			{
				if (str[i] == str[j]) dp[i][j] = dp[i + 1][j - 1];///向内考虑
				else dp[i][j] = min(min(dp[i + 1][j], dp[i][j - 1]), dp[i + 1][j - 1]) + 1;
				///删去i，删去j，修改i为j(添加与删除是一样的)
			}
		}
		printf("Case %d: %d\n", ++t, dp[0][len - 1]);
	}
	return 0;
}