【UVA】10739 - String to Palindrome（动态规划）

本文主要是介绍【UVA】10739 - String to Palindrome（动态规划），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

比较水的动态规划

dp[i][j] 将原串 i ~ j 之内的字符转化为回文字符所需要的最小操作次数

其中删除操作和添加操作本质上是一样的。

三个状态转移方程：

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

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

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

如果 i = j  dp[i][j] = 0;

14145138

10651

Pebble Solitaire

Accepted

C++

0.009

2014-09-04 09:09:42

#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<map>
#include<iostream>
using namespace std;
#define MAXD 1000 + 10
#define INF 10000
char str[MAXD];
int dp[MAXD][MAXD];
int dfs(int start,int last){if(dp[start][last] != -1)return dp[start][last];if(start == last)return dp[start][last] = 0;if(str[start] == str[last]){if(start + 1 == last)return dp[start][last] = 0;elsereturn dp[start][last] = dfs(start + 1 , last - 1);}dp[start][last] = INF;if(last - 1 >= start)dp[start][last] = min(dp[start][last],dfs(start,last - 1) + 1);if(start + 1 <= last)dp[start][last] = min(dp[start][last],dfs(start + 1, last) + 1);if(start + 1 <= last - 1)dp[start][last] = min(dp[start][last],dfs(start + 1,last - 1) + 1);return dp[start][last];
}
int main(){int T;scanf("%d",&T);for(int Case = 1; Case <= T; Case ++){scanf("%s",str);memset(dp,-1,sizeof(dp));int ans = dfs(0,strlen(str) - 1);printf("Case %d: %d\n",Case,ans);}return 0;
}

这篇关于【UVA】10739 - String to Palindrome（动态规划）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---