首页 > 代码库 > hihocoder1323 回文字符串
hihocoder1323 回文字符串
题意：一个字符串可以进行增删改一个字符，代价都是一，问最少多少代价可以得到回文字符串
题解：dp[i][j]代表i到j得到回文串的最小代价，可以得到dp式,一开始没写记忆化搜索T了
#include <bits/stdc++.h>#define ll long long#define maxn 110using namespace std;char s[maxn];int dp[maxn][maxn];inline int f(int l,int r){ if(l >= r) return 0; if(dp[l][r] != -1) return dp[l][r]; if(s[l] == s[r]) return f(l+1, r-1); return dp[l][r] = min(f(l, r-1)+1, min(f(l+1, r)+1, f(l+1, r-1)+1));}int main(){ scanf("%s", s); memset(dp, -1, sizeof(dp)); int l = strlen(s); cout<<f(0, l-1)<<endl; return 0;}
hihocoder1323 回文字符串
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。