本文主要是介绍Generating Palindromes - lightOJ 1033 区间DP回文串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：
http://www.lightoj.com/volume_showproblem.php?problem=1033
算法分析：
题意：
至少添加几个字符，能使得给定的串变为回文串。
分析：
dp[i][j]表示使给定字符串的i-j段成为回文串的最小插入字符数量，小区间推导大区间。
由内往外拓展，对于一个区间[l,r]来言，最后添加的字符肯定是l或者r，如果a[l]==a[r]，那么最少添加的字符就是dp[l+1][r-1].否则就是看最后一个是l加的少还是最后一个是r加的少，既dp[l][r]=min(dp[l+1][r],dp[l][r-1])+1;
举个例子：a b c b d
a b c b a d
a d b c b d
就看这两种情况哪一个更小了。
阶段：区间长度
状态：左右端点
决策：分情况
状态转移方程 ：
if(a[l]==a[r]) dp[l][r]=dp[l+1][r-1];
else dp[l][r]=min(dp[l+1][r],dp[l][r-1])+1;
初值：dp[i][i]=0
目标：dp[1][len]
#include<bits/stdc++.h>
using namespace std;
#define ll long long
char a[120],b[120];
int dp[120][120];
int main()
{int t;scanf("%d",&t);for(int cas=1;cas<=t;cas++){scanf("%s",a+1);int len=strlen(a+1);memset(dp,0,sizeof(dp));for(int i=1;i<=len;i++){for(int l=1;l+i-1<=len;l++){int r=l+i-1;if(a[l]==a[r])dp[l][r]=dp[l+1][r-1];elsedp[l][r]=min(dp[l+1][r],dp[l][r-1])+1;}}printf("Case %d: %d\n",cas,dp[1][len]);}return 0;
}
这篇关于Generating Palindromes - lightOJ 1033 区间DP回文串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
