首页 / 软件开发 / 数据结构与算法 / UVa 10739 String to Palindrome （DP）

UVa 10739 String to Palindrome （DP）2014-07-29 csdn博客 synapse7

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
", &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
", ++t, dp[0][len - 1]）;}return 0;}