线性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学习相关,读研读博…...
基于Flask实现的医疗保险欺诈识别监测模型
基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施,由雇主和个人按一定比例缴纳保险费,建立社会医疗保险基金,支付雇员医疗费用的一种医疗保险制度, 它是促进社会文明和进步的…...
JVM垃圾回收机制全解析
Java虚拟机(JVM)中的垃圾收集器(Garbage Collector,简称GC)是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象,从而释放内存空间,避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...
智能在线客服平台:数字化时代企业连接用户的 AI 中枢
随着互联网技术的飞速发展,消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁,不仅优化了客户体验,还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用,并…...
【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力
引言: 在人工智能快速发展的浪潮中,快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型(LLM)。该模型代表着该领域的重大突破,通过独特方式融合思考与非思考…...
零基础设计模式——行为型模式 - 责任链模式
第四部分:行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习!行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想:使多个对象都有机会处…...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...
select、poll、epoll 与 Reactor 模式
在高并发网络编程领域,高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表,以及基于它们实现的 Reactor 模式,为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。 一、I…...
什么是Ansible Jinja2
理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具,可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板,允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板,并通…...
【Linux】Linux 系统默认的目录及作用说明
博主介绍:✌全网粉丝23W,CSDN博客专家、Java领域优质创作者,掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围:SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...
比较数据迁移后MySQL数据库和OceanBase数据仓库中的表
设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...
