博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
hihocoder1323 回文字符串
阅读量:4599 次
发布时间:2019-06-09

本文共 548 字,大约阅读时间需要 1 分钟。

题意:一个字符串可以进行增删改一个字符,代价都是一,问最少多少代价可以得到回文字符串

题解:dp[i][j]代表i到j得到回文串的最小代价,可以得到dp式,一开始没写记忆化搜索T了

#include 
#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<

 

转载于:https://www.cnblogs.com/Noevon/p/7295638.html

你可能感兴趣的文章
LeetCode算法扫题系列19
查看>>
nginx获取经过层层代理后的客户端真实IP(使用正则匹配)
查看>>
YII实现dropDownList 联动事件
查看>>
搞定PHP面试 - 正则表达式知识点整理
查看>>
为什么JavaScript里面0.1+0.2 === 0.3是false
查看>>
freemarker 设置中文
查看>>
docker swarm集群搭建
查看>>
选择排序
查看>>
SQLAlchemy
查看>>
BZOJ 1303: [CQOI2009]中位数图 问题转化_扫描_思维
查看>>
SP1026 FAVDICE - Favorite Dice 数学期望
查看>>
NodeJS、NPM安装配置步骤(windows版本)
查看>>
今日内容的回顾12
查看>>
js中字符串常用熟悉和方法
查看>>
【矩阵+十进制快速幂】[NOI2013]矩阵游戏
查看>>
Java一个简单的文件工具集
查看>>
蓝牙BLE扫描成功,log中打印出扫描到的设备
查看>>
React(v16.8.4)生命周期详解
查看>>
一般处理应用页中绑定方法代码段
查看>>
React组件Components的两种表示方式
查看>>