AcWing 1015. 摘花生
Problem: AcWing 1015. 摘花生
文章目录
- 思路
- 解题方法
- 复杂度
- Code
思路
这是一个典型的动态规划问题。我们需要在一个二维网格中,从左上角走到右下角,每次只能向右或向下移动,目标是使得经过的路径上的数字之和最大。
我们可以定义dp[i][j]为从左上角走到(i, j)位置,能够得到的最大数字之和。然后我们可以根据dp[i - 1][j]和dp[i][j - 1]来更新dp[i][j]。
解题方法
我们首先初始化dp数组,然后从左上角开始,遍历每一个位置,对于每一个位置,我们都有从上面来和从左边来两种情况:如果我们从上面来,那么dp[i][j] = dp[i - 1][j] + w[i][j]。如果我们从左边来,那么dp[i][j] = dp[i][j - 1] + w[i][j]。我们取这两种情况的最大值,就是dp[i][j]的值。最后,dp[r][c]就是我们的答案。
复杂度
时间复杂度:
O ( r c ) O(rc) O(rc),因为我们需要遍历每一个位置。
空间复杂度:
O ( r c ) O(rc) O(rc),因为我们需要一个二维数组来存储dp值。
Code
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;public class Main {static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static StreamTokenizer sr = new StreamTokenizer(in);static int t, r, c, m;static int MAXN = 110;static int[][] dp = new int[MAXN][MAXN];static int[][] w = new int[MAXN][MAXN];public static void main(String[] args) throws IOException {t = nextInt();while (t-- > 0) {r = nextInt();c = nextInt();for (int i = 1; i <= r; i++) {for (int j = 1; j <= c; j++) {w[i][j] = nextInt();}}for (int i = 1; i <= r; i++) {for (int j = 1; j <= c; j++) {dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + w[i][j];}}out.println(dp[r][c]);}out.flush();}static int nextInt() throws IOException {sr.nextToken();return (int) sr.nval;}}相关文章:
AcWing 1015. 摘花生
Problem: AcWing 1015. 摘花生 文章目录 思路解题方法复杂度Code 思路 这是一个典型的动态规划问题。我们需要在一个二维网格中,从左上角走到右下角,每次只能向右或向下移动,目标是使得经过的路径上的数字之和最大。 我们可以定义dp[i][j]为从…...
Dalle-3、Sora、Stable Diffusion 3 掀起AIGC新浪潮
随着科技的飞速发展,我们迎来了视觉AIGC高光时刻,一个充满无限可能与机遇的新时代。在这个时代里,三大里程碑Dalle-3、Sora和Stable Diffusion 3以其炸裂式的技术发展,引领着AIGC领域的新浪潮。文章首先做相应简要介绍,…...
Unity 视频组件 VideoPlayer
组件添加: 在自己定义的组件下(例如:Panel) 点击 Inspector 面板中的 AddComponent ,输入“VideoPlayer”。 资源 这里 视频资源有两种形式,第一种是 VideoClip ,需要将视频文件拖拽到该属性字段…...
RSTP环路避免实验(华为)
思科设备参考:RSTP环路避免实验(思科) 一,技术简介 RSTP (Rapid Spanning Tree Protocol) 是从STP发展而来 • RSTP标准版本为IEEE802.1w • RSTP具备STP的所有功能,可以兼容STP运行 • RSTP和STP有所不同 减少了…...
Arduino IDE工程代码多文件编程和中文设置
一、esp8266模块信息 二、中英文切换 点击文件( File )–选择首选项( Preference )—选择语言( Language )—选择中文–点击确定( OK ) 三、多文件编程 在Arduino编程中,将代码分割成多个文件是一种很好的做法,特别是项目变得越来越大和复杂时。这样…...
【微服务】Eureka(服务注册,服务发现)
文章目录 1.基本介绍1.学前说明2.当前架构分析1.示意图2.问题分析 3.引出Eureka1.项目架构分析2.上图解读 2.创建单机版的Eureka1.创建 e-commerce-eureka-server-9001 子模块2.检查父子pom.xml1.子 pom.xml2.父 pom.xml 3.pom.xml 引入依赖4.application.yml 配置eureka服务5.…...
windows上ssh设置代理,直接访问公司内网
ssh设置代理一般来说很简单,对于无密码或者可以支持密钥登录的,都比较无脑 难的地方在于使用用户名密码认证来使用一个http的代理或者socks5的代理,密码如何设置?特殊字符如何处理? 直接上答案,.ssh/conf…...
C++ union用法
在C中,union是一种特殊的数据类型,可以在同一个内存位置存储不同的数据类型。它的用法如下: 1. 声明union类型:使用关键字union加上union名称来声明一个union类型。 c union UnionName { dataType1 member1; dataType2 …...
JavaSE_运算符 案例分析
/*符号在字符串中的操作: 表示连接,会将其他内容和字符串连接在一起,形成一个字符串目标:理解符号在字符串中的作用会将其他内容和字符串连接在一起,形成一个字符串*/ public class Operator03 {public static void main(String[] args) {System.out.println("5 5 "…...
15、Spring Cloud Alibaba Sentinel实现熔断与限流
注:本篇文章主要参考周阳老师讲解的cloud进行整理的! 1、Sentinel 1.1、官网 https://sentinelguard.io/zh-cn/ 等价对标 Spring Cloud Circuit Breaker 1.2、是什么 https://github.com/alibaba/Sentinel/wiki 1.3、去哪下 https://github.com/alibab…...
Linux logout命令教程:如何安全地退出Linux会话(附实例详解和注意事项)
Linux logout命令介绍 logout命令用于退出当前的登录Shell。这个命令可以被普通用户用来结束他们自己的会话。 Linux logout命令适用的Linux版本 logout命令在所有主流的Linux发行版中都是可用的,包括但不限于Debian、Ubuntu、Alpine、Arch Linux、Kali Linux、R…...
数据结构——顺序表(C语言版)
顺序表是数据结构中最基本的一种线性表,它以一段连续的存储空间来存储数据元素,元素之间的顺序由它们在内存中的位置来决定。在C语言中,我们通常使用数组来实现顺序表。 目录 顺序表的结构定义 顺序表的基本操作 应用实例 顺序表的结构定义…...
Knative 助力 XTransfer 加速应用云原生 Serverless 化
作者:元毅 公司介绍 XTransfer 是一站式外贸企业跨境金融和风控服务公司,致力于帮助中小微企业大幅降低全球展业的门槛和成本,提升全球竞争力。公司连续7年专注 B2B 外贸金融服务,已成为中国 B2B 外贸金融第一平台,目…...
服务器离线配置vscode连接,conda虚拟环境
记录一下服务器离线配置问题,以备不时之需。 服务器离线配置 vscode连接参考:vscode-server离线安装-CSDN博客 服务器离线配置conda虚拟环境:Conda 环境离线迁移(服务器断网情况下搭建虚拟环境envs) - 知乎 上次两个…...
各种需要使用的方法-->vue/微信小程序/layui
各种需要使用的方法-->vue/微信小程序/layui 1、vue里样式不起作用的方法,可以通过deep穿透的方式2、 js获取本周、上周、本月、上月日期3、ArrayBuffer Blob 格式转换ArrayBuffer与Blob的区别ArrayBuffer转BlobBlob转ArrayBuffer需要借助fileReader对象 4、使用…...
360奇酷刷机 360刷机助手 QGDP360手机QGDP刷机
360奇酷刷机 360刷机助手 QGDP破解版360手机QGDP刷机 360手机刷机资源下载链接:360rom.github.io 参考:360手机-360刷机360刷机包twrp、root 360奇酷刷机:360高通驱动安装 360手机刷机驱动;手机内置,可通过USB文件传输…...
2299. 强密码检验器 II
文章目录 题意思路代码 题意 题目链接 判断是否合法密码 思路 if 代码 class Solution { public:bool strongPasswordCheckerII(string password) {if (password.size() < 8)return false;int visit 0;for (size_t i 0; i < password.size(); i){char &ch pa…...
跟着cherno手搓游戏引擎【29】Batch简单合批
思路: CPU和GPU都开辟同样大小的一大块内存(为了存储顶点信息) 索引在程序运行时生成对应规则后绑定到索引缓冲中 动态生成顶点信息(现在改成Drawquad只是确定图形顶点的位置) 然后在Endscene,将CPU的动…...
粘包/半包及解决方案
一、粘包/半包介绍 1:粘包 粘包(Packet Concatenation)通常发生在基于流式传输协议(如 TCP)的通信中,因为 TCP 是面向流的传输协议,它不保证数据包的边界,而是将数据视为连续的字节…...
2024华为软件精英挑战赛记录
前言 本次主要是记录自己第一次参加华为软件挑战赛的经历。第一次参加比赛还是缺少经验,训练赛中拿到赛区的20多名,最后在正式赛中被反超了,只拿了40多名,实在是感到可惜。 题目:本次题目是一个智慧港口的问题。10个机…...
在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:
在 HarmonyOS 应用开发中,手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力,既支持点击、长按、拖拽等基础单一手势的精细控制,也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档,…...
在rocky linux 9.5上在线安装 docker
前面是指南,后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序
一、开发准备 环境搭建: 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 项目创建: File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...
剑指offer20_链表中环的入口节点
链表中环的入口节点 给定一个链表,若其中包含环,则输出环的入口节点。 若其中不包含环,则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...
高危文件识别的常用算法:原理、应用与企业场景
高危文件识别的常用算法:原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件,如包含恶意代码、敏感数据或欺诈内容的文档,在企业协同办公环境中(如Teams、Google Workspace)尤为重要。结合大模型技术&…...
Springboot社区养老保险系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,社区养老保险系统小程序被用户普遍使用,为方…...
Angular微前端架构:Module Federation + ngx-build-plus (Webpack)
以下是一个完整的 Angular 微前端示例,其中使用的是 Module Federation 和 npx-build-plus 实现了主应用(Shell)与子应用(Remote)的集成。 🛠️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...
C++.OpenGL (20/64)混合(Blending)
混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...
【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error
在前端开发中,JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作(如 Promise、async/await 等),开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝(r…...
uniapp 实现腾讯云IM群文件上传下载功能
UniApp 集成腾讯云IM实现群文件上传下载功能全攻略 一、功能背景与技术选型 在团队协作场景中,群文件共享是核心需求之一。本文将介绍如何基于腾讯云IMCOS,在uniapp中实现: 群内文件上传/下载文件元数据管理下载进度追踪跨平台文件预览 二…...
