线性DP(动态规划)

文章目录

  • 数字三角形
      • 思路
      • 代码
  • 最长上升子序列1
      • 思路
      • 代码
  • 最长公共子序列
      • 思路
      • 代码

其实和背包一样,都不固定,这种类型的题每一道题都需要自己从之前的经验中去摸索。

数字三角形

题目链接
在这里插入图片描述

思路

只能从左上或者右上走过来,用一个二维数组,记录到大最后一行的最大值,再进行比较
(后续可能再加几道题)

代码

#include <iostream>
#include <cstring>
using namespace std;
const int N = 510,INF = 1e9;
int n;
int a[N][N],f[N][N];
int main () 
{cin >> n;for (int i = 1;i <= n;i++) for (int j = 1;j <= i;j++)cin >> a[i][j];for (int i = 0;i <= n;i++) for (int j = 0;j <= i + 1;j++)//i要多加1,虽然最右边的右上角没有数,但是下面的方程是包括的、又因为赋值为负无穷,,所以对结果无影响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],f[i - 1][j]) + a[i][j];int res = -INF;for (int i = 1;i <= n;i++) res = max (res,f[n][i]);//比较完之后,最大值在最后一行的某一个cout << res << endl;return 0;
}

最长上升子序列1

题目链接
在这里插入图片描述

思路

数据比较小,直接比较比当前小的有几个然后进行继承

代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int n,a[N],f[N];
int main()
{cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){f[i]=1;for(int j=1;j<i;j++)if(a[j]<a[i])//比当前i小的f[i]=max(f[i],f[j]+1);//比较之后继承}int res=0;for(int i=1;i<=n;i++)res=max(res,f[i]);cout<<res<<'\n';return 0;
}

最长公共子序列

题目链接
在这里插入图片描述

思路

思路就是两个字符串慢慢比对,根据上图的注释

代码

#include<iostream>
#include<algorithm>using namespace std;
const int N=1111;
int m,n,f[N][N];
char a[N],b[N];
int main()
{cin>>n>>m;cin>>a+1>>b+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);//如果是图中的最后一种情况,最后一个字母必须相等} cout<<f[n][m]<<'\n';return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

python-A+B again

[题目描述] 小理有一个非常简单的问题给你&#xff0c;给你两个整数 A 和 B&#xff0c;你的任务是计算 AB。输入格式&#xff1a; 输入共 2∗T1 行。 输入的第一行包含一个整数 T 表示测试实例的个数&#xff0c;然后 2∗T 行&#xff0c;分别表示 A 和 B 两个正整数。注意整数…

计算机网络面试题汇总

文章目录 计算机网络基础计算机网络体系结构(网络分层模型)OSI 七层模型是什么?每一层的作用是什么?TCP/IP 四层模型是什么?每一层的作用是什么?五层体系结构以及对应的协议为什么网络要分层,分层的好处?常见网络协议有哪些,每一层常见协议有哪些?应用层有哪些常见的协…

mysql5.7安装

1.创建一个software文件 2.先下载mysql的repo源 wget http://repo.mysql.com/mysql-community-release-el7-5.noarch.rpm 3安装源包 rpm -ivh mysql-community-release-el7-5.noarch.rpm 可能会报错 改成命令 rpm -ivh mysql-community-release-el7-5.noarch.rpm --nodeps…

目标检测 | yolov6 原理和介绍

前言&#xff1a;目标检测 | yolov5 原理和介绍 后续&#xff1a; 1.简介 YOLOv6是由美团视觉智能部研发的一款目标检测框架&#xff0c;专注于工业应用&#xff0c;致力于提供极致的检测精度和推理效率。相较于YOLOv4和YOLOv5&#xff0c;YOLOv6在网络结构方面进行了深入优化…

在LabVIEW中高效读取大型CSV文件的方法

当尝试使用“读取分隔的电子表格VI”从大型CSV文件&#xff08;数百MB&#xff09;中读取数据时&#xff0c;可能会遇到内存已满错误。这是因为该VI会一次性读取整个文件并将其转换为数值数组&#xff0c;导致占用大量内存。 解决方案 可以使用“从文本文件VI读取”来部分读取…

技术探索之android项目结构

在新建项目时会自动生成很多文件&#xff0c;需要知道项目结构&#xff0c;我们需要编辑的文件的位置&#xff1a; app: 项目的代码资源都在其中&#xff0c;是我们工作的核心目录 build &#xff1a; 编译生成文件。生成的apk就在build/outputs/apk/debug里。apk在虚拟机里就…

MySQL——内置函数

时间函数 select * from msg where date_add(sendtime, interval 2 minute) > now(); 理解&#xff1a; ------------------------------|-----------|-------------|------------------ 初始时间 now() 初始时间2min 字符串 length函数返回字符串长度&#xff0c;以字节为…

【docker】docker数据卷与网络部署服务

Docker 网络模式 选择网络模式 Host Mode (主机模式) 特点: 容器与宿主机共享网络命名空间操作: docker run --nethost ... Container Mode (容器模式) 特点: 容器与指定容器共享网络命名空间操作: docker run --netcontainer:<container-id-or-name> ... None Mode (无…

营业额统计

文章目录 概要整体架构流程技术细节小结 概要 营业额统计是商业活动中一个非常重要的环节&#xff0c;它可以帮助企业了解自身的经营状况&#xff0c;并为决策提供依据。 需求分析以及接口设计 营业额统计是基于折现图来展现&#xff0c;并且按照天来展示的。实际上&#xf…

机器学习(1)--数据可视化

文章目录 数据可视化作用可视化方法实现可视化 总结 数据可视化 数据可视化是将数据以图形、图像、动画等视觉形式表示出来&#xff0c;以便人们能够更直观地理解、分析和交流数据中的信息。 作用 一个整理的好好的数据&#xff0c;我们为什么要将其可视化呢&#xff1f;将它…

苹果macOS 15 Sequoia投屏功能 实现Mac上iPhone桌面管理

8月14日消息&#xff0c;苹果最新的 iOS 18 和 macOS 15 Sequoia 测试版为 iPhone 投屏功能带来了重大更新。用户可以直接在 Mac 上管理 iPhone 桌面。 iPhone 镜像功能 macOS Sequoia最大的更新是带来了iPhone 镜像功能&#xff0c;这个功能能让给 Mac 用户将 iPhone 的屏幕镜…

异质性空间自回归模型 (HSAR)及 Stata 具体操作步骤

目录 一、引言 二、文献综述 三、理论原理 四、实证模型 五、稳健性检验 六、程序代码及解释 七、代码运行结果 一、引言 在空间计量经济学中&#xff0c;异质性空间自回归模型&#xff08;Heterogeneous Spatial Autoregressive Model&#xff0c;HSAR&#xff09;是一种…

C#去掉文件夹或文件名非法字符

实现有输入字符串创建文件夹的功能&#xff0c;需要检查字符串中是否包含不能在文件夹中使用的非法字符 。C#中如果需要生成文件路径&#xff0c;有时会抛出“文件路径中出现非法字符”的异常&#xff0c;这时我们就会找到这个非法的字符串&#xff0c;然后Replace替换掉。net类…

Linux中以单容器部署Nginx+ASP.NET Core

强烈推荐在生产环境中使用反向代理服务器转发请求到Kestrel Http服务器&#xff0c;本文将会实践将Nginx --->ASP.NET Core 部署架构容器化的过程。 Nginx->ASP.NET Coe部署架构容器化 在Docker中部署Nginx--->ASP.NETCore 有两种选择&#xff0c; 第一种是在单容器…

使用Orthofinder进行系统发育直系同源推断

Introduction 确定基因序列之间的系统发育关系是比较生物学研究的基础。它为理解地球上生命的进化和多样性提供了框架&#xff0c;并能够在生物体之间推断生物知识。鉴于此过程对生物研究多个领域的核心重要性&#xff0c;人们开发了一系列不同的软件工具&#xff0c;试图在给…

console调试

简介 浏览器的开发者工具为我们提供了强大的调试系统&#xff0c;可以用来查看DOM树结构、CSS样式调试、动画调试、JavaScript代码断点调试等。今天我们就来看看console调试的那些实用的调试技巧。 我们使用最多的就是console.log()了&#xff0c;当然多数情况下&#xff0c;…

四十二、大数据技术之Kafka3.x(5)

&#x1f33b;&#x1f33b; 目录 一、Kafka-Eagle 监控1.1 MySQL 环境准备1.2 Kafka 环境准备1.3 Kafka-Eagle 安装1.4 Kafka-Eagle 页面操作 二、集成 SpringBoot2.1 前期准备2.2 SpringBoot 生产者2.3 SpringBoot 消费者 三、集成 Spark&#xff08;拓展 Scala 语言&#xf…

IDEA快捷键(Ctrl + tab)非常好用 切换最近使用的编辑器选项卡

文章目录 1、为什么要使用 ctrl tab 快捷键&#xff1f;2、使用 ctrl tab 快捷键 1、为什么要使用 ctrl tab 快捷键&#xff1f; 当我们点击 ctrl alt 鼠标左键点击 进入方法的实现时&#xff0c;这个时候我们会在这个实现类中不断的点击&#xff0c;查看源码&#xff0c…

【学习笔记】Matlab和python双语言的学习(最小生成树——Kruskal算法、Prim算法)

文章目录 前言一、最小生成树树的一些概念关键特性最小生成树和最短路径的主要区别常用算法1. Kruskal算法(适合点多边少的图)2. Prim算法(适合边多点少的图) 二、示例三、代码实现----Matlab四、代码实现----python1. Kruskal算法2. Prim算法 总结 前言 通过模型算法&#xf…

【QuikGraph】TSP旅行商问题变体之不返回起点

1、问题分析 目的&#xff1a;在旅行商问题的基础上&#xff0c;无需返回起点。相当于找到一条最短路径&#xff0c;能够遍历所有的顶点。起点和终点都是动态计算出来的&#xff0c;不是提前固定的。 这个问题也称为为计算“最短的哈密尔顿路径”。 2、解决方案 出处&#…