区间DP及其变形写法

news/2024/6/16 4:33:47 标签: 算法, 动态规划

区间DP及其变形写法

一、模板

前言 ：

市面上的区间DP，大多都是从石子合并（链式）、石子合并（环式）开始讲起，但是笔者认为他们夹杂着前缀和，对初学者很不友好。所以我打算用另一题来引出。

P1435 [IOI2000] 回文字串

题意 ：

给定一个字符串，求出将给定字符串变成回文词所需要插入的最少字符数。

思路 ：

  • 朴素点的 ：判断一个区间是不是回文字串，是就不用插入新的字符，反之要插入新的字符。

其实经过线性DP的折磨后，大家也应该明白DP,应该由状态定义 、边界 、状态转移 几个方面组成，下面就理清这三个东西。估计对于区间dp也应该会有一个理性的认识。

/*
状态：
	回文词所需要插入的最少字符数，是关于区间长度的函数
	dp[i][j] —— 在区间从i到j，回文词所需要插入的最少字符数
边界：
	区间长度为1（len == 1） —— 必是回文字串，dp[i][i] = 0;
状态转移：
	if (s[l] == s[r])	dp[l][r] = dp[l + 1][r - 1];//s[l]和s[r]相等，不需要插入 
	else	dp[l][r] = min(dp[l + 1][r], dp[l][r - 1]) + 1;//最少字符数，只跟上一个小区间有关，要么是左边的，要么是右边
递推的写法：
	从小区间到大区间。
*/

题解 ：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull	unsigned long long
#define P pair<int, int>
#define endl '\n'
#define MaxN 0x3f3f3f3f
#define MinN -MaxN
const int mod = 1e9 + 7;

string s;

void slove(){
	cin >> s;
	int n = s.size();
	s = " " + s;//下标从1开始 
	vector<vector<int>> dp(n + 7, vector<int> (n + 7, 0));
	
	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])	dp[l][r] = dp[l + 1][r - 1];//不需要插入 
			else	dp[l][r] = min(dp[l + 1][r], dp[l][r - 1]) + 1;//从左边的区间或者右边的区间转移不过来，需要插入 
		}
	} 
	cout << dp[1][n];//1 ~ n 范围内的最小插入 
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int t = 1;
//	cin >> t;
	while (t--){
		slove();
	}
    return 0;
}

二、区间合并型（割点k——大区间分成两部分）

前言 :

本来是现在把石子合并放到这讲的，但是发现了另一个好题。能诠释==（割点k——大区间分成两部分）== ，也不用再讲前缀和增加理解负担。

P4170 [CQOI2007]涂色

题意 ：

把一段连续的木板涂成一个给定的颜色，求解最少的涂色次数

思路 ：

  • 朴素点的 ：既然已经学过区间dp了，直接想能不能定义其状态。
/*
状态：
	最少的涂色次数。关于区间的函数
	dp[l][r]
边界：
	区间长度 len == 1、l == r 时。只需涂一次色， dp[i][i] = 1
	求最少的涂色次数	其他初始化为MaxN
状态转移：
	状态转移：
	s[i] == s[j]	
		dp[l][r] = min(dp[l + 1][r], dp[l][r - 1]);//过大上次涂的边界即可，不需要再涂 
	else 
		dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);// 我们需要考虑将子串断成两部分来涂色，需要枚举子串的断点
*/

题解 ：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull	unsigned long long
#define P pair<int, int>
#define endl '\n'
#define MaxN 0x3f3f3f3f
#define MinN -MaxN
const int mod = 1e9 + 7;

void slove(){
	string s;
	cin >> s;
	int n = s.size();
	s = " " + s;
	vector<vector<int >> dp(n + 7, vector<int>(n + 7, MaxN));//初始化
    
	for (int i = 1; i <= n; i++)	dp[i][i] = 1;//边界

	for (int len = 2; len <= n; len++){//len从2开始，1已经遍历过了
		for (int l = 1; l + len - 1 <= n; l++){
			int r = l + len - 1;
			if (s[l] == s[r])	dp[l][r] = min(dp[l + 1][r], dp[l][r - 1]);
			else	for (int k = l; k < r; k++)	dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]); 
		}
	}
	cout << dp[1][n];
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int t = 1;
//	cin >> t;
	while (t--){
		slove();
	}
    return 0;
}

三、区间合并型（加入前缀和的应用）

前言：

终于到激动人心的时候了！石子合并！这里提一嘴，石子合并有链式和环式，现在先将链式。

P1775 石子合并（弱化版）

题意 ：

合并的代价为这两堆石子的质量之和，求总的代价最小

思路 ：

  • 朴素点的 ：如果是两个石头合并很容易，就两个相加就好了。但是他是一个区间，那怎么求？对嘛！铺垫这么久的前缀和就登场了！
  • 前缀和求重量，如果求[i, j]的重量，preS[j] - preS[i - 1];
/*
状态：
    总的代价最小，关于区间的函数
    dp[i][j]
边界：
	dp[i][i] = 0//不合并，没有代价
	求总的代价最小	其他初始化为MaxN
状态转移：
	两堆原先的重量，再加合并的重量
	dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r] + s[r] - s[l - 1]);
*/

题解 ：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull	unsigned long long
#define P pair<int, int>
#define endl '\n'
const int mod = 1e9 + 7;
const int maxl = 3 * 1e2 + 7;

int n;

void slove(){
	cin >> n;
	vector<int> a(n + 1, 0), s(n + 1, 0);//a ——存数， s ——前缀和 
	vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0x3f3f3f3f));
	
	for (int i = 1; i <= n; i++){//从下标1开始 
		cin >> a[i];
		s[i] = s[i - 1] + a[i];
		dp[i][i] = 0;
	}
	
	for (int len = 2; len <= n; len++){//枚举区间长度 
		for (int l = 1; l + len - 1 <= n; l++){//移动区间、范围[l,l + len) 
			int r = l + len - 1;
			for (int k = l; k < r; k++){//这个区间分成两个部分，[l, k] ~ [k + 1, r] ,这里是k + 1所以 k < r 
				dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r] + s[r] - s[l - 1]);
			}
		}
	}
	cout << dp[1][n];
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int t = 1;
//	cin >> t;
	while (t--){
		slove();
	}
    return 0;
}

四、环型DP的处理方式

前言 ：

环形dp，其实不难，就多复制了一维，其他都一样的

P1880 [NOI1995] 石子合并

题意 ：

合并的代价为这两堆石子的质量之和，求总的代价最小

首尾可以相连成环

思路：

  • 朴素点的 ：如果是两个石头合并很容易，就两个相加就好了。但是他是一个区间，那怎么求？对嘛！铺垫这么久的前缀和就登场了！
  • 前缀和求重量，如果求[i, j]的重量，preS[j] - preS[i - 1];
  • 多复制一维，从n -> 2n，解决成环问题

题解 ：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull	unsigned long long
#define P pair<int, int>
#define endl '\n'
#define MaxN 0x3f3f3f3f
#define MinN -MaxN
const int mod = 1e9 + 7;

int n;

void slove(){
	cin >> n;
	vector<vector<int>> dpMax(n * 2 + 7, vector<int> (2 * n + 7, MinN)), dpMin(n * 2 + 1, vector<int> (2 * n + 1, MaxN));
	vector<int> s(2 * n + 7, 0), a(2 * n + 7, 0);
	
	for (int i = 1; i <= n; i++){
		cin >> a[i];
		a[i + n] = a[i];
	}
	
	for (int i = 1; i <= 2 * n; i++){
		s[i] = s[i - 1] + a[i];
		dpMax[i][i] = 0;
		dpMin[i][i] = 0;
	}
	
	for (int len = 2; len <= n; len++){
		for (int l = 1; l + len - 1 <= 2 * n; l++){
			int r = l + len - 1;
			for (int k = l; k < r; k++){
				dpMax[l][r] = max(dpMax[l][r], dpMax[l][k] + dpMax[k + 1][r] + s[r] - s[l - 1]);
				dpMin[l][r] = min(dpMin[l][r], dpMin[l][k] + dpMin[k + 1][r] + s[r] - s[l - 1]);
			}
		}
	}
	
	int maxAns = MinN, minAns = MaxN;
	for (int i = 1; i <= n; i++){
		minAns = min(minAns, dpMin[i][i + n - 1]);
		maxAns = max(maxAns, dpMax[i][i + n - 1]);
//		cout << maxAns << endl;
	}
	cout << minAns << endl << maxAns << endl;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int t = 1;
//	cin >> t;
	while (t--){
		slove();
	}
    return 0;
}

五、环型DP的处理方式 —— 去除前缀和，普通的环

前言 ：

前缀和，区间长度为n,但是如果不是前缀和，区间长度就要变成n + 1

P1063 [NOIP2006 提高组] 能量项链

题意 ：

和石子合并差不多，只不过那个是相加，这个是相乘

思路 ：

和石子合并一个思路不多赘述，唯一一个点就是不用前缀和，首尾相连的话，区间范围为n + 1,包含首尾相连

题解 ：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull	unsigned long long
#define P pair<int, int>
#define endl '\n'
#define MaxN 0x3f3f3f3f
#define MinN -MaxN
const int mod = 1e9 + 7;

int n, ans = 0;

void slove(){
	cin >> n;
	vector<int> a(2 * n + 7, 0);
	vector<vector<int>> dp(2 * n + 7, vector<int>(2 * n + 7, 0));
	for (int i = 1; i <= n; i++)	cin >> a[i], a[i + n] = a[i];
	
	for (int len = 3; len <= n + 1; len++){
		for (int l = 1; l + len - 1 <= 2 * n; l++){
			int r = l + len - 1;
			for (int k = l  +1; k < r; k++)	dp[l][r] = max(dp[l][r], dp[l][k] + dp[k][r] + a[l] * a[k] * a[r]);
		}
	}
	
	for (int i = 1; i <= n; i++)	ans = max(ans, dp[i][i + n]);
	
	cout << ans;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int t = 1;
//	cin >> t;
	while (t--){
		slove();
	}
    return 0;
}

六、结语

完结散花，如有不明白欢迎私信交流。都看到这了，给个三连呗！


http://www.niftyadmin.cn/n/318387.html

相关文章

【Vector VN1630/40 I/O应用】-1-简易示波器

【Vector VN1630/40 I/O应用】-1-简易示波器

案例背景(共13页精简)&#xff1a;该篇博客将告诉您&#xff1a; Vector VN1630A&#xff0c;VN1640A&#xff0c;VH6501 I/O的使用&#xff1b;将Vector VN1630A/VN1640A CAN/LIN Interface的I/O接口充当一个简易的“示波器”使用&#xff1b;观察“CAN唤醒”工作的ECU控制器…
阅读更多...
常见指标总结(持续总结中......)

常见指标总结(持续总结中......)

数据分析的基础是业务指标体系&#xff0c;搭建好的指标体系就得了解指标具体含义&#xff0c;本文持续分享总结常见指标名词释义&#xff0c;欢迎各位评论区补充扩展&#xff01; pv是page view的缩写&#xff0c;即页面浏览量&#xff0c;通常是衡量一个网络新闻频道或网站甚…
阅读更多...
软测人正在杀死软测行业

软测人正在杀死软测行业

前言、一个软件做出来&#xff0c;最不能少的人是谁&#xff1f; 不用说就是开发&#xff0c;因为开发是最了解软件运作的那个人&#xff0c;早期不少一人撸网站或者APP的例子&#xff0c;相当于一个人同时是产品、研发、测试、运维等等&#xff0c;这也是为何开发是地位和上限…
阅读更多...
股票量价关系基础知识2

股票量价关系基础知识2

内盘与外盘 外盘&#xff0c;是指在一个交易日获某段交易时间内&#xff0c;买方主动提价以委卖价成交的股数之和&#xff0c;也称为主动性买盘 内盘&#xff0c;是指在一个交易日获某段交易时间内&#xff0c;卖方主动降价以委买价成交的股数之和&#xff0c;也称主动性卖盘。…
阅读更多...
代码随想录算法训练营第59天|● 503.下一个更大元素II ● 42. 接雨水

代码随想录算法训练营第59天|● 503.下一个更大元素II ● 42. 接雨水

503.下一个更大元素II 题目链接&#xff1a;503.下一个更大元素II 题目描述&#xff1a; 给定一个循环数组 nums (nums[nums.length - 1] 的下一个元素是 nums[0] &#xff09;&#xff0c;返回 nums 中每个元素的 下一个更大元素 。 数字 x 的 下一个更大的元素 是按数组遍历…
阅读更多...
字符编码与java中的 数字前缀

字符编码与java中的 数字前缀

在了解字符编码时, 扩展了解到 转义字符 \x 表示ASCII编码 \u 表示Unicode编码 数字前缀, java语言 0开头, 默认是八进制 0x开头, 16进制 0b开头, 二进制 正则 \d 表示整数 UTF-8 编码与 MySQL 中的 utf8、utf8mb4 - beihai blog UTF-8 是变长字节编码方式。对于某一个…
阅读更多...
自学大语言模型的应用程序框架Langchain（初入门）

自学大语言模型的应用程序框架Langchain（初入门）

现阶段chatGPT非常火热。带动了第三方开源库&#xff1a;LangChain火热。它是一个在大语言模型基础上实现联网搜索并给出回答、总结 PDF 文档、基于某个 Youtube 视频进行问答等等的功能的应用程序。 什么是Langchain LangChain 是一个用于开发由语言模型驱动的应用程序的框架…
阅读更多...
进程组，会话的基础概念，以及进程组，会话，控制终端，前台后台之间的联系（系列文章第二篇）

进程组，会话的基础概念，以及进程组，会话，控制终端，前台后台之间的联系（系列文章第二篇）

前言 这个系列的文章有三篇&#xff0c;其目的是为了搞清楚&#xff1a; 进程&#xff0c;shell&#xff0c;shell进程&#xff0c;终端&#xff0c;控制终端&#xff0c;前台进程&#xff0c;后台进程&#xff0c;控制进程&#xff0c;前台进程组&#xff0c;后台进程组&#…
阅读更多...
最新文章

Copyright @ 2022~2023