计科余定成

用户名：dotcpp0598358

访问量：15767

签　名：

孙蕾，我好喜欢你啊，为了你我要把键盘敲烂!!!

等　　级
排　　名	41
经　　验	13043
参赛次数	1
文章发表	69
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

我是余定成

TA的其他文章

刻录光盘（c++）
浏览：66

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （Java代码）

蓝桥杯2016年第七届真题-密码脱落（区间DP）

　　作者: 计科余定成　　　　发表时间：2023-05-22 18:30:40 浏览：207　|　评论：1　

原题链接：蓝桥杯2016年第七届真题-密码脱落

### 题目大意
给定一个字符串，最少插入多少的字符可以使得字符串变成`回文串`
### 解题思路

思想：区间DP

状态定义：$$f[l][r]$$ 表示把从$$l$$ 到$$r$$的字符串变为回文串的最少插入字符数

状态转移：当$$s[l]==s[r]$$时，说明两端已经满足回文条件，则转移到除两端外的字符串,即$$f[l][r]=f[l+1][r-1]$$
当$$s[l]  != [r]$$时，说明需要再插入一个字符，可以是左端插入，也可以是右端插入，即$$ f[l][r] = min(f[l][r - 1], f[l + 1][r])+1$$

答案：根据定义答案就是$$f[1][n]$$

### 参考代码
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;

int n;
string s;
int f[N][N];

int main() {
	cin >> s;
	n = s.size();//获取字符串长度
	s = ' ' + s;//个人习惯下标从1开始

for (int len = 1; len <= n; len++) {//枚举区间长度
		for (int l = 1; l + len - 1 <= n; l++) {//枚举左端点
			int r = l + len - 1;
			if (s[l] == s[r]) f[l][r] = f[l + 1][r - 1];
			else f[l][r] = min(f[l][r - 1], f[l + 1][r]) + 1;
		}
	}

cout << f[1][n];
	return 0;
}

```

无注释
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;

int n;
string s;
int f[N][N];

int main() {
	cin >> s;
	n = s.size();
	s = ' ' + s;

for (int len = 1; len <= n; len++) {
		for (int l = 1; l + len - 1 <= n; l++) {
			int r = l + len - 1;
			if (s[l] == s[r]) f[l][r] = f[l + 1][r - 1];
			else f[l][r] = min(f[l][r - 1], f[l + 1][r]) + 1;
		}
	}

cout << f[1][n];
	return 0;
}

```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

H2430612014

2024-11-16 22:56:16

计科余定成

TA的其他文章

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （Java代码）

上车人数（C语言代码）

数字整除（C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C++代码）

蓝桥杯2016年第七届真题-密码脱落（区间DP）

评论区

精彩推荐

printf基础练习2 （C++代码）（受教了，，%#o和%#x的用途）三人行，必有我师，，多看题解会有收获

A+B for Input-Output Practice (VI) （C++代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

DNA （C语言代码）

1050题解（结构体数组与结构体指针的使用）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

1025题初学者，求帮忙看下,不知道哪错了

计科余定成

TA的其他文章

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （Java代码）

上车人数 （C语言代码）

数字整除 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C++代码）

蓝桥杯2016年第七届真题-密码脱落（区间DP）

评论区

精彩推荐

printf基础练习2 （C++代码）（受教了，，%#o和%#x的用途）三人行，必有我师，，多看题解会有收获

A+B for Input-Output Practice (VI) （C++代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

DNA （C语言代码）

1050题解（结构体数组与结构体指针的使用）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

1025题 初学者，求帮忙看下,不知道哪错了

上车人数（C语言代码）

数字整除（C语言代码）

　　评论区

1025题初学者，求帮忙看下,不知道哪错了