NYOJ37、1023、15(回文串、括号匹配、记忆化搜索、dp，区间dp)

2024-04-05 23:38
文章标签 dp 15 搜索 括号 匹配 回文 记忆 区间 1023 nyoj37

本文主要是介绍NYOJ37、1023、15(回文串、括号匹配、记忆化搜索、dp，区间dp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 

回文字符串

时间限制：3000 ms  |  内存限制：65535 KB

难度：4

输入

第一行给出整数N（0<N<100）
接下来的N行，每行一个字符串，每个字符串长度不超过1000.

输出

每行输出所需添加的最少字符数

样例输入

1
Ab3bd

样例输出

2

描述

所谓回文字符串，就是一个字符串，从左到右读和从右到左读是完全一样的，比如"aba"。当然，我们给你的问题不会再简单到判断一个字符串是不是回文字符串。现在要求你，给你一个字符串，可在任意位置添加字符，最少再添加几个字符，可以使这个字符串成为回文字符串。

这题是2000IOI题。

想了半天，终于AC了，开心~~~。

定义状态 dp[i][j] 表示 区间 i-j 内最少添加的字符个数。

则容易得到状态转移方程

dp[i][j] =\left\{\begin{matrix} min(dp[i+1][j],dp[i][j-1]) + 1 \\ dp[i+1][j-1] \qquad s.t\;(a[i] == a[j]) \end{matrix}\right.

即当 a[i] == a[j]  时候，不增加计数，否则增加计数

 

code（记忆化搜索）：

 

#include<iostream>
#include<stdio.h>
#include<vector>
#include<map>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<set>
#include<cmath>
using namespace std;
const int N = 1000+5;
int dp[N][N];
char a[N];int rec(int i, int j){if(i >= j)return dp[i][j] = 0;if(dp[i][j] != -1)return dp[i][j];int & ans = dp[i][j];if(a[i] == a[j])ans = rec(i+1,j-1);elseans = min(rec(i+1,j),rec(i,j-1)) + 1;return ans;
}int main(){int t;scanf("%d",&t);while(t--){memset(dp,-1,sizeof(dp));scanf("%s",a);int ans = rec(0,strlen(a)-1);printf("%d\n",ans);}return 0;}

看了其他代码，似乎还有种方法，是求反转串与原串最长公共子序列，答案就是原串的长度减去最长公共子串的长度。

和我的思路不大一样。

 

这题可以用另一种方法，就是把原字符串取反，然后和原串求最长公共子串，然后用总长度减去最长公共子串长度，得到的即为结果。

可以理解最长公共子串为不添加字符即满足条件的字符，其它的需要在对称位置添加字符。

code2(最长公共子串)：

#include<iostream>
#include<stdio.h>
#include<vector>
#include<map>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<set>
#include<cmath>
using namespace std;
const int N = 1005;
char s1[N],s2[N];
int dp[N][N];int main(){int t,len;scanf("%d",&t);while(t--){memset(dp,0,sizeof(dp));scanf("%s",&s1[1]);len = strlen(&s1[1]);for(int i = len; i > 0; --i){s2[i] = s1[len-i+1];}for(int i = 1; i <= len; ++i){for(int j = 1; j <= len; ++j){if(s1[i] == s2[j]){dp[i][j] = dp[i-1][j-1] + 1;}else{dp[i][j] = max(dp[i-1][j],dp[i][j-1]);}}}printf("%d\n",len-dp[len][len]);}return 0;}

 

区间dp思想

尝试写的递推（超时了）：

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<vector>
#include<map>
#include<algorithm>
#include<string>
using namespace std;const int N = 1000+5;
int dp[N][N];
const int INF = 1 << 30;
char a[N];int main(){int t;scanf("%d",&t);int len;while(t--){memset(dp,INF,sizeof(dp));scanf("%s",a);len = strlen(a);for(int i = 0; i < len; ++i){for(int j = 0; j < len; ++j){if(i >= j)dp[i][j] = 0;}}bool flag = true;for(int i = 0; i < len; ++i){if(a[i] != a[len-i-1])flag = false;}if(flag){printf("%d\n",0);continue;}for(int l = 2; l <= len; ++l){for(int i = 0; i + l <= len; ++i){int j = i+l-1;for(int k = i; k < j; ++k){if(a[i] == a[j]){dp[i][j] = dp[i+1][j-1];}elsedp[i][j] = min(dp[i+1][j],dp[i][j-1]) + 1;}}}printf("%d\n",dp[0][len-1]);}return 0;}

还是回文

时间限制：2000 ms  |  内存限制：65535 KB

难度：3

输入

多组数据
第一个有两个数n,m，分别表示字符的种数和字符串的长度
第二行给出一串字符，接下来n行，每行有一个字符(a~z)和两个整数，分别表示添加和删除这个字符的花费
所有数都不超过2000

输出

最小花费

样例输入

3 4
abcb
a 1000 1100
b 350 700
c 200 800

样例输出

900

描述

判断回文串很简单，把字符串变成回文串也不难。现在我们增加点难度，给出一串字符(全部是小写字母)，添加或删除一个字符，都会产生一定的花费。那么，将字符串变成回文串的最小花费是多少呢？

 

这题为什么这句不被放在 else里，而是总是执行？

dp[i][j] = min(dp[i+1][j]+cost[s[i]],dp[i][j-1]+cost[s[j]]) \\式1

原因：

例如 求 abaa  可以转化为 求aba （去除右边的a） 和 ba (去除两侧的a因为他们想等，可以去除)

但是如果 如果 式1 被放在else里面了， 就不同时考虑上面 aba 与ba 这两情况了，前者操作花费为 a, 后者花费为右侧侧添加b

这显然是不同的花费，但是如果添加了else，这就只会单独被考虑一种(取决于 语句顺序)。

其实可以理解为，总是要考虑着两种情况的，只是有一种情况考虑之前需要满足a[i] == a[j]  所以才加上的if语句。

并不是为了把两种情况单独分开考虑。

code1：

注意dp必须要初始化为0  ，这是为了服务于 i >= j 时候 结果为 0 设计的

#include<iostream>
#include<stdio.h>
#include<vector>
#include<map>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<set>
#include<cmath>
using namespace std;
const int N = 2000 + 5;
char s[N];
int cost[200];
int dp[N][N];
int main(){int n,m,x,y;char ss[2];while(scanf("%d%d",&n,&m) != EOF){scanf("%s",s);for(int i = 1; i <= n; ++i){scanf("%s%d%d",ss,&x,&y);cost[ss[0]] = min(x,y);}memset(dp,0,sizeof(dp));for(int l = 2; l <= m; ++l){for(int i = 0; i < m-l+1; ++i){int j = i+l-1;dp[i][j] = min(dp[i+1][j]+cost[s[i]],dp[i][j-1]+cost[s[j]]);if(s[i] == s[j])dp[i][j] = min(dp[i+1][j-1],dp[i][j]);}}printf("%d\n",dp[0][m-1]);}return 0;}

另一种递推式写法：

两种遍历的次序不同，但是异曲同工

           memset(dp,0,sizeof(dp));for(int j = 1; j < m; ++j){for(int i = j-1; i >= 0; --i){dp[i][j] = min(dp[i+1][j]+cost[s[i]],dp[i][j-1]+cost[s[j]]);if(s[i] == s[j])dp[i][j] = min(dp[i+1][j-1],dp[i][j]);}}

 

另外、这题用记忆化搜索超时了（可能是频繁的memset(dp) 超时？）

code(超时)：

#include<iostream>
#include<stdio.h>
#include<vector>
#include<map>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<set>
#include<cmath>
using namespace std;
const int N = 200;
//int del[N],add[N];
int cost[N];
char ts[2];
int dp[2000+5][2000+5];
char s[2000+5];
const int INF = 1 << 30;int rec(int i, int j){if(i >= j)return 0;if(dp[i][j] >= 0)return dp[i][j];int & ans = dp[i][j];ans = min(rec(i+1,j)+cost[s[i]],rec(i,j-1)+cost[s[j]]);if(s[i] == s[j])ans = rec(i+1,j-1);//ans = min(min(rec(i+1,j)+add[s[i]],rec(i+1,j)+del[s[i]]),min(rec(i,j-1)+add[s[j]],rec(i,j-1)+del[s[j]]));return ans;
}int main(){int n,m;char c;int x,y;while(~scanf("%d%d",&n,&m)){memset(dp,-1,sizeof(dp));getchar();scanf("%s",&s);for(int i = 0; i < n; ++i){getchar();scanf("%s%d%d",&ts,&x,&y);cost[ts[0]] = min(x,y);}printf("%d\n",rec(0,m-1));}return 0;}

题三（括号匹配）

code1（记忆化搜索）

#include<iostream>
#include<stdio.h>
#include<vector>
#include<map>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<set>
#include<cmath>
using namespace std;
const int N = 100+5;
int dp[N][N];
bool vis[N][N];
char s[100+5];int rec(int i,int j){if(i > j)return 0;if(i == j)return 1; // 说明 没有匹配if(vis[i][j])return dp[i][j];int & ans = dp[i][j];if(s[i] == '(' && s[j] == ')' || s[i] == '[' && s[j] == ']')ans = min(ans,rec(i+1,j-1));if(s[i] == '(' || s[i] == '[')ans = min(ans,rec(i+1,j)+1);if(s[j] == ')' || s[j] == ']')ans = min(ans,rec(i,j-1)+1);for(int k = i; k < j; ++k){ans = min(ans,rec(i,k)+rec(k+1,j));}vis[i][j] = true; //求出dp[i][j] 后标记 为 truereturn ans;
}int main(){int t;scanf("%d",&t);while(t--){memset(vis,false,sizeof(vis));memset(dp,0x3f,sizeof(dp)); //初始化为无穷大scanf("%s",s);printf("%d\n",rec(0,strlen(s)-1));}return 0;}

注意两者的 dp 初始化方式不同、但本质一样、这里面也是一样 if语句之间不能加else、每种情况都需要考虑。

code2(递推):

#include<iostream>
#include<stdio.h>
#include<vector>
#include<map>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<set>
#include<cmath>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 100+5;
int dp[N][N];
char s[N];int main(){int t,len;scanf("%d",&t);while(t--){memset(dp,0,sizeof(dp));scanf("%s",s);len = strlen(s);for(int i = 0; i < len; ++i){for(int j = 0; j < len; ++j){if(i == j)dp[i][j] = 1;else if(i > j)dp[i][j] = 0;elsedp[i][j] = INF;}}for(int l = 1; l <= len; ++l){for(int i = 0; i < len-l+1; ++i){int j = i+l-1;if(s[i] == '(' && s[j] == ')' || s[i] == '[' && s[j] == ']')dp[i][j] = min(dp[i+1][j-1],dp[i][j]);if(s[i] == '(' || s[i] == '[')dp[i][j] = min(dp[i+1][j]+1,dp[i][j]);if(s[j] == ')' || s[j] == ']')dp[i][j] = min(dp[i][j],dp[i][j-1]+1);for(int k = i; k < j; ++k){dp[i][j] = min(dp[i][k]+dp[k+1][j],dp[i][j]);//切分的情况}}}printf("%d\n",dp[0][len-1]);}return 0;}

 

这篇关于NYOJ37、1023、15(回文串、括号匹配、记忆化搜索、dp，区间dp)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/878458。

相关文章

Nginx location匹配模式与规则详解

Nginx location匹配模式与规则详解

《Nginxlocation匹配模式与规则详解》：本文主要介绍Nginxlocation匹配模式与规则,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、环境二、匹配模式1. 精准模式2. 前缀模式（不继续匹配正则）3. 前缀模式（继续匹配正则）4. 正则模式（大
阅读更多...
Java 正则表达式URL 匹配与源码全解析

Java 正则表达式URL 匹配与源码全解析

《Java正则表达式URL匹配与源码全解析》在Web应用开发中,我们经常需要对URL进行格式验证,今天我们结合Java的Pattern和Matcher类,深入理解正则表达式在实际应用中... 目录1.正则表达式分解：2. 添加域名匹配 (2)3. 添加路径和查询参数匹配 (3) 4. 最终优化版本5.设计思
阅读更多...
Python中使用正则表达式精准匹配IP地址的案例

Python中使用正则表达式精准匹配IP地址的案例

《Python中使用正则表达式精准匹配IP地址的案例》Python的正则表达式(re模块)是完成这个任务的利器,但你知道怎么写才能准确匹配各种合法的IP地址吗,今天我们就来详细探讨这个问题,感兴趣的朋... 目录为什么需要IP正则表达式？IP地址的基本结构基础正则表达式写法精确匹配0-255的数字验证IP地
阅读更多...
浅谈配置MMCV环境,解决报错,版本不匹配问题

浅谈配置MMCV环境,解决报错,版本不匹配问题

《浅谈配置MMCV环境,解决报错,版本不匹配问题》：本文主要介绍浅谈配置MMCV环境,解决报错,版本不匹配问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录配置MMCV环境,解决报错,版本不匹配错误示例正确示例总结配置MMCV环境,解决报错,版本不匹配在col
阅读更多...
详解nginx 中location和 proxy_pass的匹配规则

详解nginx 中location和 proxy_pass的匹配规则

《详解nginx中location和proxy_pass的匹配规则》location是Nginx中用来匹配客户端请求URI的指令,决定如何处理特定路径的请求,它定义了请求的路由规则,后续的配置（如... 目录location 的作用语法示例：location /www.chinasem.cntestproxy
阅读更多...
Python使用DeepSeek进行联网搜索功能详解

Python使用DeepSeek进行联网搜索功能详解

《Python使用DeepSeek进行联网搜索功能详解》Python作为一种非常流行的编程语言,结合DeepSeek这一高性能的深度学习工具包,可以方便地处理各种深度学习任务,本文将介绍一下如何使用P... 目录一、环境准备与依赖安装二、DeepSeek简介三、联网搜索与数据集准备四、实践示例：图像分类1.
阅读更多...
Nginx中location实现多条件匹配的方法详解

Nginx中location实现多条件匹配的方法详解

《Nginx中location实现多条件匹配的方法详解》在Nginx中,location指令用于匹配请求的URI,虽然location本身是基于单一匹配规则的,但可以通过多种方式实现多个条件的匹配逻辑... 目录1. 概述2. 实现多条件匹配的方式2.1 使用多个 location 块2.2 使用正则表达式
阅读更多...
C++实现回文串判断的两种高效方法

C++实现回文串判断的两种高效方法

《C++实现回文串判断的两种高效方法》文章介绍了两种判断回文串的方法：解法一通过创建新字符串来处理,解法二在原字符串上直接筛选判断,两种方法都使用了双指针法,文中通过代码示例讲解的非常详细,需要的朋友... 目录一、问题描述示例二、解法一：将字母数字连接到新的 string思路代码实现代码解释复杂度分析三、
阅读更多...
golang字符串匹配算法解读

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt（KMP）算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串（称为
阅读更多...
C++使用栈实现括号匹配的代码详解

C++使用栈实现括号匹配的代码详解

《C++使用栈实现括号匹配的代码详解》在编程中,括号匹配是一个常见问题,尤其是在处理数学表达式、编译器解析等任务时,栈是一种非常适合处理此类问题的数据结构,能够精确地管理括号的匹配问题,本文将通过C+... 目录引言问题描述代码讲解代码解析栈的状态表示测试总结引言在编程中，括号匹配是一个常见问题，尤其是在
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2