本文主要是介绍POjnbsp;1159nbsp;nbsp;nbsp;Palindromenbsp;(dp),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
http://acm.pku.edu.cn/JudgeOnline/problem?id=1159
这个题有两种基本解法,第1种方法:
设a[i][j]表示从第i个字符到第j个字符需要增加多少字母使得回文,初始化后,状态转移方程:
if(s[i]==s[j])
a[i][j]=a[i+1][j-1];
else
a[i][j]=min(a[i+1][j],a[i][j-1])+1;
注意内存限制。用short型刚刚好。
第2种解法:
此题可转换成求最长回文子串
即S与^S的最长公共子序列,则answer=n-LCS(S,^S).
这个题有两种基本解法,第1种方法:
设a[i][j]表示从第i个字符到第j个字符需要增加多少字母使得回文,初始化后,状态转移方程:
if(s[i]==s[j])
else
注意内存限制。用short型刚刚好。
第2种解法:
此题可转换成求最长回文子串
即S与^S的最长公共子序列,则answer=n-LCS(S,^S).
#include<stdio.h>
#include<string.h>
int min(int a,int b)
{
return a>b?b:a;
}
int map[2][5005];
int main()
{
char str[5005];
int n,i,j;
while(scanf("%d",&n)!=EOF)
{
scanf("%s",str+1);
memset(map,0,sizeof(map));
for(i=n;i>=1;i--)
{
for(j=1+i;j<=n;j++)
if(str[i]==str[j])
map[i%2][j]=map[(i+1)%2][j-1];
else map[i%2][j]=min(map[(i+1)%2][j],map[i%2][j-1])+1;
}
printf("%d\n",map[1][n]);
}
return 0;
}
这篇关于POjnbsp;1159nbsp;nbsp;nbsp;Palindromenbsp;(dp)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!