我是靠谱客的博主 玩命冥王星,这篇文章主要介绍hihocoder 1323 回文字符串(字符串+dp),现在分享给大家,希望可以做个参考。

题解:

比较水的题目

dp[i][j]表示[i...j]最少改变几次变成回文字符串

那么有三种转移

dp[i][j] = dp[i+1][j-1] + s[i] != s[j]

dp[i][j] = dp[i+1][j] + 1(删除左边的字符,或者在右边添加一个字符与左边匹配)

dp[i][j] = dp[i][j-1] + 1(删除右边的字符,或者在左边添加一个字符与右边匹配)

 

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
char S[110];
int dp[110][110];
int dfs(int i, int j){
if(i >= j) return 0;
if(dp[i][j] < 100) return dp[i][j];
dp[i][j] = min(dp[i][j], dfs(i+1, j) + 1);
dp[i][j] = min(dp[i][j], dfs(i, j-1) + 1);
dp[i][j] = min(dp[i][j], dfs(i+1, j-1) + (S[i] != S[j]));
return dp[i][j];
}
int main()
{
while(cin>>S){
int n = strlen(S);
memset(dp, 1, sizeof(dp));
cout<<dfs(0, n-1)<<endl;
}
return 0;
}

 

转载于:https://www.cnblogs.com/Saurus/p/7374758.html

最后

以上就是玩命冥王星最近收集整理的关于hihocoder 1323 回文字符串(字符串+dp)的全部内容,更多相关hihocoder内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(57)

评论列表共有 0 条评论

立即
投稿
返回
顶部