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。

相关文章

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+... 目录引言问题描述代码讲解代码解析栈的状态表示测试总结引言在编程中，括号匹配是一个常见问题，尤其是在
阅读更多...
关于Gateway路由匹配规则解读

关于Gateway路由匹配规则解读

《关于Gateway路由匹配规则解读》本文详细介绍了SpringCloudGateway的路由匹配规则,包括基本概念、常用属性、实际应用以及注意事项,路由匹配规则决定了请求如何被转发到目标服务,是Ga... 目录Gateway路由匹配规则一、基本概念二、常用属性三、实际应用四、注意事项总结Gateway路由
阅读更多...
Springboot的ThreadPoolTaskScheduler线程池轻松搞定15分钟不操作自动取消订单

Springboot的ThreadPoolTaskScheduler线程池轻松搞定15分钟不操作自动取消订单

《Springboot的ThreadPoolTaskScheduler线程池轻松搞定15分钟不操作自动取消订单》：本文主要介绍Springboot的ThreadPoolTaskScheduler线... 目录ThreadPoolTaskScheduler线程池实现15分钟不操作自动取消订单概要1，创建订单后
阅读更多...
C# ComboBox下拉框实现搜索方式

C# ComboBox下拉框实现搜索方式

《C#ComboBox下拉框实现搜索方式》文章介绍了如何在加载窗口时实现一个功能,并在ComboBox下拉框中添加键盘事件以实现搜索功能,由于数据不方便公开,作者表示理解并希望得到大家的指教... 目录C# ComboBox下拉框实现搜索步骤一步骤二步骤三总结C# ComboBox下拉框实现搜索步骤一这
阅读更多...
Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya（不是本人，claude AI）在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容： 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用
阅读更多...
这15个Vue指令，让你的项目开发爽到爆

这15个Vue指令，让你的项目开发爽到爆

1. V-Hotkey 仓库地址: github.com/Dafrok/v-ho… Demo: 戳这里 https://dafrok.github.io/v-hotkey 安装: npm install --save v-hotkey 这个指令可以给组件绑定一个或多个快捷键。你想要通过按下 Escape 键后隐藏某个组件，按住 Control 和回车键再显示它吗？小菜一碟： <template
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2