首页 > 代码库 > 南洋理工oj 37
南洋理工oj 37
思路：
输入字符串S;设sum要插入字符的最小值
从两端出发前端x=0；后端y=L-1;
首先，如果S[0]!=S[L-1],此时要么在最前面添字符，要么在末尾添字符，sum++；（这是无法避免的）
然后，S[0]=S[L-1],此时前端x +1，后端y-1；
注意递归出口：前段>后端(x>y)，此时为0；
递归算法最重要的是先明确函数的参数含义以及函数实现的功能。这题是实现在pos=x到pos=y这段字符要添加的最小字符数
还有数组保存递归结果的模板
#include<stdio.h>
#include<string.h>
#define min(a,b) (a<b?a:b)
char a[1001];
int f[1001][1001];
int dp(int x,int y)
{
if(f[x][y]!=-1)
return f[x][y];
if(x>=y)
{
f[x][y]=0;
return f[x][y];
}
if(a[x]==a[y])
{
f[x][y]=dp(x+1,y-1);
return f[x][y];
}
f[x][y]=min(dp(x+1,y),dp(x,y-1))+1;
return f[x][y];
}
int main()
{
int N;
scanf("%d",&N);
while(N--)
{
scanf("%s",a);
memset(f,-1,sizeof(f));
printf("%d\n",dp(0,strlen(a)-1));
}
return 0;
}
南洋理工oj 37
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。