当前位置: 首页 > news >正文

线性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问题首先考虑状态转移方程&#xff0c;定义一个集合f ( i , j) &#xff0c;表示从第一个数字&#xff08;1,1&#xff09;走到第 i行&#xff0c;第 j列&#xff08;i , j&#xff09;的所有方案的集合&#xff0c…...

SpringMVC

SpringMVC配置 引入Maven依赖 &#xff08;springmvc&#xff09;web.xml配置DispatcherServlet配置 applicationContext 的 MVC 标记开发Controller控制器 几点注意事项&#xff1a; 在web.xml中 配置<load-on-startup> 0 </load-on-startup> 会自动创建Spring…...

C++模板基础(二)

函数模板&#xff08;二&#xff09; ● 模板实参的类型推导 – 如果函数模板在实例化时没有显式指定模板实参&#xff0c;那么系统会尝试进行推导 template<typename T> void fun(T input, T input2) {std::cout << input << \t << input2 << …...

什么是linux内核态、用户态?

目录标题为什么需要区分内核空间与用户空间内核态与用户态如何从用户空间进入内核空间整体结构为什么需要区分内核空间与用户空间 在 CPU 的所有指令中&#xff0c;有些指令是非常危险的&#xff0c;如果错用&#xff0c;将导致系统崩溃&#xff0c;比如清内存、设置时钟等。如…...

day8—选择题

文章目录1.Test.main() 函数执行后的输出是&#xff08;D&#xff09;2. JUnit主要用来完成什么&#xff08;D&#xff09;3.下列选项中关于Java中super关键字的说法正确的是&#xff08;A&#xff09;1.Test.main() 函数执行后的输出是&#xff08;D&#xff09; public clas…...

ngx错误日志error_log配置

ngx之error_log 日志配置格式&#xff1a; 常见的错误日志级别 错误日志可配置位置 关闭error_log配置 设置debug 日志级别的前提&#xff1a; ngx之error_log 日志配置格式&#xff1a; error_log 存放路径 日志级别 例&#xff1a; error_log /usr/local/log…...

1.11、自动化

自动化 一、java 手机自动化 首先new DesertCapabilities&#xff08;这是一个类&#xff09; setCapability – 设置信息 获取appium的驱动对象 new AppiumDriver – 本机IP地址:端口号/wd/hub,前面的设置值信息 driver.findElementById() – 通过id找位置 click() – 点击 &…...

函数的定义与使用及七段数码管绘制

函数的定义 函数是一段代码的表示 函数是一段具有特定功能的、可重用的语句组 函数是一种功能的抽象&#xff0c;一般函数表达特定功能 两个作用&#xff1a;降低编程难度 和 代码复用 求一个阶乘 fact就是 函数名 n就是参数 return就是输出部分即返回值 而函数的调用就是…...

怎么压缩pdf文件大小?pdf文件太大如何压缩?

喜爱看小说的小伙伴们都会在网上下载很多的pdf格式电子书以方便随时阅览&#xff0c;但是pdf的电子书一般都过于的冗长&#xff0c;下载后的储存也是一个问题&#xff0c;怎么pdf压缩大小呢&#xff1f;可以试试今天介绍的这款pdf在线压缩工具来进行pdf压缩&#xff08;https:/…...

阿里云Linux服务器登录名ecs-user和root选择问题

阿里云服务器Linux系统登录名可以选择root或ecs-user&#xff0c;root具有操作系统的最高权限&#xff0c;但是root会导致的安全风险比较大&#xff0c;ecs-user比较安全&#xff0c;但是如果系统后续依赖root权限就会比较麻烦&#xff0c;从安全的角度&#xff0c;建议选择ecs…...

【云原生】 初体验阿里云Serverless应用引擎SAE(三),挂载配置文件使应用的配置和运行的镜像解耦

目录 一、前言二、SAE配置1、创建配置项2、配置SAE Nginx服务效果1、【云原生】 初体验阿里云Serverless应用引擎SAE(一),部署Nginx服务 2、【云原生】 初体验阿里云Serverless应用引擎SAE(二),前端Nginx静态文件持久化到对象存储OSS 本篇 3、【云原生】 初体验阿里云Se…...

Oracle用户密码过期,修改永不过期

修改密码有效过期时间&#xff0c;可以通过以下四步设置&#xff0c;如果再第一步发现本身的密码过期时间为无限期的&#xff0c;那就请各位小伙伴绕过&#xff0c;如果发现不是无期限的&#xff0c;那么必须设置第四步&#xff0c;才会生效。 目录 第一步&#xff1a;查询密码…...

welearn 视听说1-4

词汇题&#xff08;55道&#xff09; 1. You should carefully think over_____ the manager said at the meeting. A. that B. which C. what D. whose 1.选C,考察宾语从句连接词&#xff0c;主句谓语动词think over后面缺宾语&#xff0c;后面的宾语从句谓语动…...

【git】将本地项目同步到远程

前提&#xff1a;git已经安装&#xff0c;并与账号完成密钥绑定 在github上创建一个新仓库 在项目文件夹下&#xff0c;右击选择git bash here &#xff0c;打开一个终端对话框 git init (在项目目录下出现隐藏的.git文件夹&#xff0c;目的是把该项目文件夹变成git可管理…...

10-链表练习-LeetCode82删除排序链表中的重复元素II

题目 给定一个已排序的链表的头 head &#xff0c; 删除原始链表中所有重复数字的节点&#xff0c;只留下不同的数字 。返回已排序的链表 。 示例 1&#xff1a; 输入&#xff1a;head [1,2,3,3,4,4,5] 输出&#xff1a;[1,2,5] 示例 2&#xff1a; 输入&#xff1a;head …...

贯穿设计模式第五话--接口隔离原则

&#x1f973;&#x1f973;&#x1f973; 茫茫人海千千万万&#xff0c;感谢这一刻你看到了我的文章&#xff0c;感谢观赏&#xff0c;大家好呀&#xff0c;我是最爱吃鱼罐头&#xff0c;大家可以叫鱼罐头呦~&#x1f973;&#x1f973;&#x1f973; 从今天开始&#xff0c;将…...

C语言计算机二级/C语言期末考试 刷题(四)

在空闲时间整理了一些C语言计算机二级和C语言期末考试题库 整理不易&#xff0c;大家点赞收藏支持一下 祝大家计算机二级和期末考试都高分过 系列文章&#xff1a; C语言计算机二级/C语言期末考试 刷题&#xff08;一&#xff09; C语言计算机二级/C语言期末考试 刷题&#x…...

JDK8中Stream接口的常用方法

参考答案 Stream 接口中的方法分为中间操作和终端操作&#xff0c;具体如下。 中间操作&#xff1a; filter&#xff1a;过滤元素map&#xff1a;映射&#xff0c;将元素转换成其他形式或提取信息flatMap&#xff1a;扁平化流映射limit&#xff1a;截断流&#xff0c;使其元…...

ThingsBoard源码解析-数据订阅与规则链数据处理

前言 结合本篇对规则链的执行过程进行探讨 根据之前对MQTT源码的学习&#xff0c;我们由消息的处理入手 //org.thingsboard.server.transport.mqtt.MqttTransportHandlervoid processRegularSessionMsg(ChannelHandlerContext ctx, MqttMessage msg) {switch (msg.fixedHeade…...

探究Transformer模型中不同的池化技术

❤️觉得内容不错的话&#xff0c;欢迎点赞收藏加关注&#x1f60a;&#x1f60a;&#x1f60a;&#xff0c;后续会继续输入更多优质内容❤️&#x1f449;有问题欢迎大家加关注私戳或者评论&#xff08;包括但不限于NLP算法相关&#xff0c;linux学习相关&#xff0c;读研读博…...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南

精益数据分析&#xff08;97/126&#xff09;&#xff1a;邮件营销与用户参与度的关键指标优化指南 在数字化营销时代&#xff0c;邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天&#xff0c;我们将深入解析邮件打开率、网站可用性、页面参与时…...

分布式增量爬虫实现方案

之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面&#xff0c;避免重复抓取&#xff0c;以节省资源和时间。 在分布式环境下&#xff0c;增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路&#xff1a;将增量判…...

rnn判断string中第一次出现a的下标

# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...

Netty从入门到进阶(二)

二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架&#xff0c;用于…...

力扣热题100 k个一组反转链表题解

题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...

Caliper 负载(Workload)详细解析

Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...

【LeetCode】算法详解#6 ---除自身以外数组的乘积

1.题目介绍 给定一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O…...