算法学习18:动态规划

算法学习18:动态规划


文章目录

  • 算法学习18:动态规划
  • 前言
  • 一、线性DP
    • 1.数字三角形:f[i][j] = max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j]);
    • 2.1最长上升子序列:f[i] = max(f[i], f[j] + 1);
    • 2.2 打印出最长子序列
    • 3.最长公共子序列:
  • 二、区间dp:
    • 1.石子合并:
  • 总结


前言


在这里插入图片描述


提示:以下是本篇文章正文内容:

一、线性DP

1.数字三角形:f[i][j] = max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j]);



在这里插入图片描述



在这里插入图片描述



// 给定一个数字三角形,从顶部出发,在每一个结点可以选择移动至左下方或者是右下方的结点,
// 直到移动到底层,要求找到一条路径,使得路径上的数字的和最大。
// 输入:第一行包含一个整数n,表示数字三角形的层数
// 接下来的n行,每行包含若干整数,其中第i行表示数字三角形第i层包含的整数。

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510, INF = 1e9;// (相对的)正无穷 

int n;
int a[N][N];// 存出数字三角形
int f[N][N];// 状态 

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++)
		for(int j = 1; j <= i; j ++)
			scanf("%d", &a[i][j]);
	
	// 初始化
	// 注意1:对于左右边界,都要多处理一次。(i+1)		
	for(int i = 0; i <= n; i ++)
		for(int j = 0; j <= i + 1; j ++)
			f[i][j] = -INF;// 负无穷 
			
	f[1][1] = a[1][1];
	for(int i = 2; i <= n; i ++)
		for(int j = 1; j <= i; j ++)
			f[i][j] = max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j]);
			
	int res = -INF;
	// 遍历最后一层,找到答案 
	for(int i = 1; i <= n; i ++) res = max(res, f[n][i]);
	
	printf("%d\n", res);
	return 0;
 } 


在这里插入图片描述



在这里插入图片描述



2.1最长上升子序列:f[i] = max(f[i], f[j] + 1);



在这里插入图片描述



2.2 打印出最长子序列


// 给定一个长度为n的数列,求数值“严格递增”的子序列的长度最长时多少?

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n;
int a[N], f[N], g[N];// 数列   状态  存储i是由那个状态转移过来的。 

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
	
	for(int i = 1; i <= n; i ++)
	{
		f[i] = 1;// 只有a[i]一个数
		g[i] = 0; 
		for(int j = 1; j < i; j ++)
			// 保证递增:a[j] 是 a[i] 的前一个数 
			if(a[j] < a[i])
				if(f[i] < f[j] + 1)
					{
						// 更新 
						f[i] = f[j] + 1;
						// 记录一下f[i] 是从哪一个状态转移过来的。 
						g[i] = j;
					}		
	}
	// 找到答案的下标 
	int k = 1;
	for(int i = 1; i <= n; i ++)
		if(f[k] < f[i]) 	
			k = i;
			
	printf("%d\n", f[k]);// 长度 
	
	for(int i = 0, len = f[k]; i < len; i ++)
	{
		printf("%d ", a[k]);
		// 根据g数组可以知道f[k]是从那个状态转移的 
		k = g[k];
	}
	
	return 0;
}


在这里插入图片描述



// 给定一个长度为n的数列,求数值“严格递增”的子序列的长度最长时多少?

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n;
int a[N], f[N];// 数列   状态 

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
	
	for(int i = 1; i <= n; i ++)
	{
		f[i] = 1;// 只有a[i]一个数
		for(int j = 1; j < i; j ++)
			// 保证递增:a[j] 是 a[i] 的前一个数 
			if(a[j] < a[i])
				f[i] = max(f[i], f[j] + 1); 
	}
	
	int res = 0;
	// 便利所有f[i] 
	for(int i = 1; i <= n; i ++)  res = max(res, f[i]);
	
	printf("%d", res);
	return 0;
}


在这里插入图片描述



在这里插入图片描述



3.最长公共子序列:


在这里插入图片描述



在这里插入图片描述



// 给定两个长度分别为n和m的字符串A和B,
// 求即是A的子序列又是B的子序列的字符串的长度最长是多少?
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
char a[N], b[N];// 2个字符串 
int f[N][N]; 

int main()
{
	scanf("%d%d", &n, &m);
	scanf("%s%s", a + 1, b + 1);// 注意1:从a[1]开始输入字符串
	// 从1开始遍历 
	for(int i = 1; i <= n; i ++)
		for(int j = 1; j <= m; j ++)
		{
			f[i][j] = max(f[i - 1][j], f[i][j - 1]);
			if(a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
		 } 
		 
	printf("%d\n", f[n][m]);
	return 0;
}

在这里插入图片描述



二、区间dp:

1.石子合并:


在这里插入图片描述



在这里插入图片描述



在这里插入图片描述



在这里插入图片描述



// 设有n堆石子排成一排,其编号为1,2,3,......,n
// 用一个整数描述每堆石子的质量,现在要将这n堆石子合并为一堆。

// 例子1:有1 3 5 2四堆石子,我们可以先合并1、2堆,代价为4,得到4 5 2,又合并1、2堆,
// 代价为9,得到9 2,在合并得到11,总代价:4+9+11=24
// 例子2:先合并1和2、3和4堆,代价为4+7,得到4 7,再合并,代价为11,总代价:4+7+11=22
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 310;

int n;
int s[N];// 原始数据 
int f[N][N];

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++) scanf("%d", &s[i]);
	// 前缀和数组: 
	for(int i = 1; i <= n; i ++) s[i] += s[i - 1];
	
	// 按长度从小到大枚举所有状态:从2开始 
	// 区间长度为1:不需要代价 
	for(int len = 2; len <= n; len ++)
		// 枚举起点: 
		for(int i = 1; i + len - 1 <= n; i ++)
		{
			// 左右端点: 
			int l = i, r = i + len - 1;
			f[l][r] = 1e8;// 要初始化为一个比较大的数!!!  
			// 枚举分界点: 
			for(int k = 1; k < r; k ++)
				f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
		}
	
	printf("%d\n", f[1][n]);
	return 0;
 } 

在这里插入图片描述


总结

提示:这里对文章进行总结:

💕💕💕

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/519488.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

[从零开始学习Redis | 第九篇] 深入了解Redis数据类型

前言&#xff1a; 在现代软件开发中&#xff0c;数据存储和处理是至关重要的一环。为了高效地管理数据&#xff0c;并实现快速的读写操作&#xff0c;各种数据库技术应运而生。其中&#xff0c;Redis作为一种高性能的内存数据库&#xff0c;广泛应用于缓存、会话存储、消息队列…

MySQL - 基础三

11、事务管理 CURD不加控制&#xff0c;会有什么问题&#xff1f; 当客户端A检查还有一张票时&#xff0c;将票卖掉&#xff0c;还没有执行更新数据库时&#xff0c;客户端B检查了票数&#xff0c;发现大于0&#xff0c;于是又卖了一次票。然后A将票数更新回数据库。这是就出现…

09 flink-sql 中基于 mysql-cdc 的 select * from test_user 的具体实现

前言 这也是最近帮一个朋友看问题 遇到的一个问题 然后 引发了一下 对于 flink-sql 里面的一些 常规处理的思考, 理解 原始问题主要是 在测试库可以使用 flink-sql 可以正常同步, 但是 在生产环境 无法正常同步数据 这个问题 我们后面单独 记录一篇文章 测试用例 下载…

设计模式总结-外观模式(门面模式)

外观模式 模式动机模式定义模式结构外观模式实例与解析实例一&#xff1a;电源总开关实例二&#xff1a;文件加密 模式动机 引入外观角色之后&#xff0c;用户只需要直接与外观角色交互&#xff0c;用户与子系统之间的复杂关系由外观角色来实现&#xff0c;从而降低了系统的耦…

携程旅行 abtest

声明: 本文章中所有内容仅供学习交流使用&#xff0c;不用于其他任何目的&#xff0c;抓包内容、敏感网址、数据接口等均已做脱敏处理&#xff0c;严禁用于商业用途和非法用途&#xff0c;否则由此产生的一切后果均与作者无关&#xff01;wx a15018601872 本文章…

WindowsPowerShell安装配置Vim的折腾记录

说明 vim一直以来都被称为编辑器之神一样的存在。但用不用vim完全取决于你自己&#xff0c;但是作为一个学计算机的同学来说&#xff0c;免不了会和Linux打交道&#xff0c;而大部分的Linux操作系统都预装了vim作为编辑器&#xff0c;如果是简单的任务&#xff0c;其实vim只要会…

c/c++之编译链接

了解我们写的代码是如何转变成可执行文件.exe的是很有必要的&#xff0c;我们将这些底层的东西掌握清楚才能打好基础&#xff0c;筑高楼。 编译链接的全流程 我们平时写代码的文件是.c或者.cpp文件。这里面包括我们的代码&#xff0c;还有宏定义&#xff0c;引用头文件以及注…

齐护机器人方位传感器指南针罗盘陀螺仪

一、方位传感器原理及功能说明 齐护方位传感器是一款集成了三轴磁传感器芯片的方位传感器模块。适用于无人机、机器人、移动和个人手持设备中的罗盘&#xff08;指南针&#xff09;、导航和游戏等高精度应用。模块可以感应XYZ平面角度外&#xff0c;还可实现1至2的水平面角度罗…

Python--Django--说明

Django 是基于python 的 Web 开发框架. &nsbp;   Web开发指的是开发基于B/S 架构, 通过前后端的配合, 将后台服务器上的数据在浏览器上展现给前台用户的应用. &nsbp;   在早期, 没有Web框架的时候, 使用 Python CGI 脚本显示数据库中的数据. Web框架致力于解决一些…

考古:IT架构演进之IOE架构

考古&#xff1a;IT架构演进之IOE架构 IOE架构&#xff08;IBM, Oracle, EMC&#xff09;出现在20世纪末至21世纪初&#xff0c;是一种典型的集中式架构体系。在这个阶段&#xff0c;企业的关键业务系统往往依赖于IBM的小型机&#xff08;后来还包括大型机&#xff09;、Oracle…

后端灰度发布

在软件开发中&#xff0c;"灰度"通常指的是渐进式地将新功能、更新或改进引入到生产环境中&#xff0c;但只对一小部分用户或流量进行部署和测试的过程。这种方法允许开发团队在生产环境中逐步测试新功能&#xff0c;以确保其稳定性、可靠性和用户体验&#xff0c;同…

vscode+anaconda 环境python环境

环境说明&#xff1a; windows 10 vscodeanaconda anaconda 安装&#xff1a; 1、官网下载地址:Free Download | Anaconda 2、安装 接受协议&#xff0c;选择安装位置&#xff0c;一直next&#xff0c;到下面这一步&#xff0c;上面是将Anaconda 添加至环境变量&#xff0…

非关系型数据库--------------------Redis 群集模式

目录 一、集群原理 二、集群的作用 &#xff08;1&#xff09;数据分区 &#xff08;2&#xff09;高可用 Redis集群的作用和优势 三、Redis集群的数据分片 四、Redis集群的工作原理 五、搭建redis群集模式 5.1启用脚本配置集群 5.2修改集群配置 5.3启动redis节点 5…

自动驾驶涉及相关的技术

当科幻走进现实&#xff0c;当影视照进生活&#xff0c;无数次憧憬的自动驾驶&#xff0c;正在慢慢的梦想成真。小时候天马星空的想象&#xff0c;现在正悄无声息的改变着我们的生活。随着汽车电动化进程的加快&#xff0c;自动驾驶技术映入眼帘&#xff0c;很多人可能感觉遥不…

非关系型数据库------------Redis的安装和部署

目录 一、关系型数据库与非关系型数据库 1.1关系型数据库 1.2非关系型数据库 1.2.1非关系型数据库产生背景 1.3关系型非关系型区别 1.4客户访问时&#xff0c;关系型数据库与redis的工作过程 二、Redis 2.1redis简介 2.2Redis命中机制和淘汰机制 2.3Redis 具有以下优…

每天五分钟深度学习:深度学习中数据样本和标签的符号化表示

本文重点 在深度学习的研究与应用中&#xff0c;数据样本和标签的符号化表示是至关重要的一环。通过合理的符号化表示&#xff0c;我们可以将现实世界中的数据转化为计算机能够理解和处理的形式&#xff0c;从而为后续的模型训练和推理提供基础。本文将对深度学习中数据样本和…

基于SpringBoot和Vue的校园周边美食探索以及分享系统

今天要和大家聊的是基于SpringBoot和Vue的校园周边美食探索以及分享系统 &#xff01;&#xff01;&#xff01; 有需要的小伙伴可以通过文章末尾名片咨询我哦&#xff01;&#xff01;&#xff01; &#x1f495;&#x1f495;作者&#xff1a;李同学 &#x1f495;&#x1f…

Hadoop-入门

资料来源&#xff1a;尚硅谷-Hadoop 一、Hadoop 概述 1.1 Hadoop 是什么 1&#xff09;Hadoop是一个由Apache基金会所开发的分布式系统基础架构。 2&#xff09;主要解决&#xff1a;海量数据的存储和海量数据的分析计算问题。 3&#xff09;广义上来说&#xff0c;Hadoop…

文件服务器之二:SAMBA服务器

文章目录 什么是SAMBASAMBA的发展历史与名称的由来SAMBA常见的应用 SAMBA服务器基础配置配置共享资源Windows挂载共享Linux挂载共享 什么是SAMBA 下图来自百度百科 SAMBA的发展历史与名称的由来 Samba是一款开源的文件共享软件&#xff0c;它基于SMB&#xff08;Server Messa…

wordpress全站开发指南-面向开发者及深度用户(全中文实操)--php函数

php函数 wordpress会封装一部分函数&#xff0c;比如bloginfo该函数的作用是直接调用你设置的你的网站的名称 示例 This is our amazing custom theme <?php echo 22; function myfirstfunction(){ echo 33; echo "<p>Hello ,this is my first function</…