线性DP——AcWing 898. 数字三角形、AcWing 895. 最长上升子序列
AcWing 898. 数字三角形
1.题目

898. 数字三角形
2.思路
DP问题首先考虑状态转移方程,定义一个集合f ( i , j) ,表示从第一个数字(1,1)走到第 i行,第 j列(i , j)的所有方案的集合,那么我们要求的就是其中方案的整数之和的最大值。
这个点可以由左上方(i−1 , j)走过来,即f( i-1, j)+a(i , j)
这个点也可以由右上方(i−1,j−1)走过来,即f( i-1, j-1)+a(i , j)
所以状态转移方程就是f(i , j)=max{ f( i-1, j) , f( i-1, j-1) } + a(i , j)
这个思路是从上往下算,当向下走的时候,需要考虑边界问题。也就是对于f[2][1]的时候,f[1]f[0]并没有设置这个值,默认为0,题中的数字有负数,则会出现错误的最大值。需要对于f进行重置,置为Integer.MIN_VALUE,同样也可以从下往上算
3.Ac代码
思路一
import java.util.Arrays;
import java.util.Scanner;public class Main {static int N=510;static int [][]a=new int[N][N]; //存储每一层数字static int [][]f=new int[N][N]; //从第一个数字走到第 i行,第 j列元素的方案集合public static void main(String[] args) {Scanner sc=new Scanner(System.in);int n=sc.nextInt();for (int i = 1; i <=n; i++) {for (int j = 1; j <=i; j++) {a[i][j]=sc.nextInt();}}//因为可能这个数的上面左右两边都没有数,添加一个默认值for (int i = 0; i <=n; i++) {for (int j = 0; j <=i+1; j++) {f[i][j]=Integer.MIN_VALUE;}}//第一个方案只有这一种情况f[1][1]=a[1][1];for (int i=2; i<=n; i++){for(int j=1;j<=i;j++){f[i][j]=Math.max(f[i-1][j-1],f[i-1][j]) + a[i][j];}}int res=Integer.MIN_VALUE;for(int i=1;i<=n;i++){res=Math.max(res,f[n][i]);}System.out.println(res);}
}
思路二
import java.util.Arrays;
import java.util.Scanner;public class Main {static int N=510;static int [][]a=new int[N][N]; //存储每一层数字static int [][]f=new int[N][N]; //从第一个数字走到第 i行,第 j列元素的方案集合public static void main(String[] args) {Scanner sc=new Scanner(System.in);int n=sc.nextInt();for (int i = 1; i <=n; i++) {for (int j = 1; j <=i; j++) {a[i][j]=sc.nextInt();}}for (int i = n; i >= 1; i--) {//从最后一排开始走,从下往上。for (int j = 1; j <= i; j++) {f[i][j] = Math.max(f[i + 1][j + 1], f[i + 1][j]) + a[i][j];}}System.out.println(f[1][1]);}
}
AcWing 895. 最长上升子序列
1.题目

895. 最长上升子序列
2.思路
首先还是考虑状态表示,定义一个fi 表示从第一个数开始算,以第 i个数结尾的最长上升子序列,如果我们选第1个数,那么对应的就是f1
如果我们选第2个数,那么对应的就是f2
如果我们选第j个数,那么对应的就是f j
所以状态转移方程就是f i=max (f i +1)
3.Ac代码
import java.util.Scanner;public class Main {static int N=1010;static int []a=new int[N]; //存储数组static int []f=new int[N]; //fi 表示从第一个数开始算,以第 i个数结尾的最长上升子序列public static void main(String[] args) {Scanner sc=new Scanner(System.in);int n=sc.nextInt();for (int i = 1; i <=n; i++) {a[i]=sc.nextInt();}int res=0;for (int i = 1; i <=n; i++) {f[i]=1;for (int j = 1; j < i; j++) {if(a[j]<a[i]){f[i]=Math.max(f[i],f[j]+1);}}res=Math.max(res,f[i]);}System.out.println(res);}
}
感谢你能看完,如果对你有帮助的话,点个赞支持下
相关文章:
线性DP——AcWing 898. 数字三角形、AcWing 895. 最长上升子序列
AcWing 898. 数字三角形 1.题目 898. 数字三角形 2.思路 DP问题首先考虑状态转移方程,定义一个集合f ( i , j) ,表示从第一个数字(1,1)走到第 i行,第 j列(i , j)的所有方案的集合,…...
SpringMVC
SpringMVC配置 引入Maven依赖 (springmvc)web.xml配置DispatcherServlet配置 applicationContext 的 MVC 标记开发Controller控制器 几点注意事项: 在web.xml中 配置<load-on-startup> 0 </load-on-startup> 会自动创建Spring…...
C++模板基础(二)
函数模板(二) ● 模板实参的类型推导 – 如果函数模板在实例化时没有显式指定模板实参,那么系统会尝试进行推导 template<typename T> void fun(T input, T input2) {std::cout << input << \t << input2 << …...
什么是linux内核态、用户态?
目录标题为什么需要区分内核空间与用户空间内核态与用户态如何从用户空间进入内核空间整体结构为什么需要区分内核空间与用户空间 在 CPU 的所有指令中,有些指令是非常危险的,如果错用,将导致系统崩溃,比如清内存、设置时钟等。如…...
day8—选择题
文章目录1.Test.main() 函数执行后的输出是(D)2. JUnit主要用来完成什么(D)3.下列选项中关于Java中super关键字的说法正确的是(A)1.Test.main() 函数执行后的输出是(D) public clas…...
ngx错误日志error_log配置
ngx之error_log 日志配置格式: 常见的错误日志级别 错误日志可配置位置 关闭error_log配置 设置debug 日志级别的前提: ngx之error_log 日志配置格式: error_log 存放路径 日志级别 例: error_log /usr/local/log…...
1.11、自动化
自动化 一、java 手机自动化 首先new DesertCapabilities(这是一个类) setCapability – 设置信息 获取appium的驱动对象 new AppiumDriver – 本机IP地址:端口号/wd/hub,前面的设置值信息 driver.findElementById() – 通过id找位置 click() – 点击 &…...
函数的定义与使用及七段数码管绘制
函数的定义 函数是一段代码的表示 函数是一段具有特定功能的、可重用的语句组 函数是一种功能的抽象,一般函数表达特定功能 两个作用:降低编程难度 和 代码复用 求一个阶乘 fact就是 函数名 n就是参数 return就是输出部分即返回值 而函数的调用就是…...
怎么压缩pdf文件大小?pdf文件太大如何压缩?
喜爱看小说的小伙伴们都会在网上下载很多的pdf格式电子书以方便随时阅览,但是pdf的电子书一般都过于的冗长,下载后的储存也是一个问题,怎么pdf压缩大小呢?可以试试今天介绍的这款pdf在线压缩工具来进行pdf压缩(https:/…...
阿里云Linux服务器登录名ecs-user和root选择问题
阿里云服务器Linux系统登录名可以选择root或ecs-user,root具有操作系统的最高权限,但是root会导致的安全风险比较大,ecs-user比较安全,但是如果系统后续依赖root权限就会比较麻烦,从安全的角度,建议选择ecs…...
【云原生】 初体验阿里云Serverless应用引擎SAE(三),挂载配置文件使应用的配置和运行的镜像解耦
目录 一、前言二、SAE配置1、创建配置项2、配置SAE Nginx服务效果1、【云原生】 初体验阿里云Serverless应用引擎SAE(一),部署Nginx服务 2、【云原生】 初体验阿里云Serverless应用引擎SAE(二),前端Nginx静态文件持久化到对象存储OSS 本篇 3、【云原生】 初体验阿里云Se…...
Oracle用户密码过期,修改永不过期
修改密码有效过期时间,可以通过以下四步设置,如果再第一步发现本身的密码过期时间为无限期的,那就请各位小伙伴绕过,如果发现不是无期限的,那么必须设置第四步,才会生效。 目录 第一步:查询密码…...
welearn 视听说1-4
词汇题(55道) 1. You should carefully think over_____ the manager said at the meeting. A. that B. which C. what D. whose 1.选C,考察宾语从句连接词,主句谓语动词think over后面缺宾语,后面的宾语从句谓语动…...
【git】将本地项目同步到远程
前提:git已经安装,并与账号完成密钥绑定 在github上创建一个新仓库 在项目文件夹下,右击选择git bash here ,打开一个终端对话框 git init (在项目目录下出现隐藏的.git文件夹,目的是把该项目文件夹变成git可管理…...
10-链表练习-LeetCode82删除排序链表中的重复元素II
题目 给定一个已排序的链表的头 head , 删除原始链表中所有重复数字的节点,只留下不同的数字 。返回已排序的链表 。 示例 1: 输入:head [1,2,3,3,4,4,5] 输出:[1,2,5] 示例 2: 输入:head …...
贯穿设计模式第五话--接口隔离原则
🥳🥳🥳 茫茫人海千千万万,感谢这一刻你看到了我的文章,感谢观赏,大家好呀,我是最爱吃鱼罐头,大家可以叫鱼罐头呦~🥳🥳🥳 从今天开始,将…...
C语言计算机二级/C语言期末考试 刷题(四)
在空闲时间整理了一些C语言计算机二级和C语言期末考试题库 整理不易,大家点赞收藏支持一下 祝大家计算机二级和期末考试都高分过 系列文章: C语言计算机二级/C语言期末考试 刷题(一) C语言计算机二级/C语言期末考试 刷题&#x…...
JDK8中Stream接口的常用方法
参考答案 Stream 接口中的方法分为中间操作和终端操作,具体如下。 中间操作: filter:过滤元素map:映射,将元素转换成其他形式或提取信息flatMap:扁平化流映射limit:截断流,使其元…...
ThingsBoard源码解析-数据订阅与规则链数据处理
前言 结合本篇对规则链的执行过程进行探讨 根据之前对MQTT源码的学习,我们由消息的处理入手 //org.thingsboard.server.transport.mqtt.MqttTransportHandlervoid processRegularSessionMsg(ChannelHandlerContext ctx, MqttMessage msg) {switch (msg.fixedHeade…...
探究Transformer模型中不同的池化技术
❤️觉得内容不错的话,欢迎点赞收藏加关注😊😊😊,后续会继续输入更多优质内容❤️👉有问题欢迎大家加关注私戳或者评论(包括但不限于NLP算法相关,linux学习相关,读研读博…...
业务系统对接大模型的基础方案:架构设计与关键步骤
业务系统对接大模型:架构设计与关键步骤 在当今数字化转型的浪潮中,大语言模型(LLM)已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中,不仅可以优化用户体验,还能为业务决策提供…...
日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...
C++初阶-list的底层
目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...
【WiFi帧结构】
文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成:MAC头部frame bodyFCS,其中MAC是固定格式的,frame body是可变长度。 MAC头部有frame control,duration,address1,address2,addre…...
相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了: 这一篇我们开始讲: 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下: 一、场景操作步骤 操作步…...
Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)
目录 1.TCP的连接管理机制(1)三次握手①握手过程②对握手过程的理解 (2)四次挥手(3)握手和挥手的触发(4)状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...
家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...
屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!
5月28日,中天合创屋面分布式光伏发电项目顺利并网发电,该项目位于内蒙古自治区鄂尔多斯市乌审旗,项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站,总装机容量为9.96MWp。 项目投运后,每年可节约标煤3670…...
第25节 Node.js 断言测试
Node.js的assert模块主要用于编写程序的单元测试时使用,通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试,通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...
如何在最短时间内提升打ctf(web)的水平?
刚刚刷完2遍 bugku 的 web 题,前来答题。 每个人对刷题理解是不同,有的人是看了writeup就等于刷了,有的人是收藏了writeup就等于刷了,有的人是跟着writeup做了一遍就等于刷了,还有的人是独立思考做了一遍就等于刷了。…...
