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

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 思路 这是一个典型的动态规划问题。我们需要在一个二维网格中&#xff0c;从左上角走到右下角&#xff0c;每次只能向右或向下移动&#xff0c;目标是使得经过的路径上的数字之和最大。 我们可以定义dp[i][j]为从…...

Dalle-3、Sora、Stable Diffusion 3 掀起AIGC新浪潮

随着科技的飞速发展&#xff0c;我们迎来了视觉AIGC高光时刻&#xff0c;一个充满无限可能与机遇的新时代。在这个时代里&#xff0c;三大里程碑Dalle-3、Sora和Stable Diffusion 3以其炸裂式的技术发展&#xff0c;引领着AIGC领域的新浪潮。文章首先做相应简要介绍&#xff0c…...

Unity 视频组件 VideoPlayer

组件添加&#xff1a; 在自己定义的组件下&#xff08;例如&#xff1a;Panel&#xff09; 点击 Inspector 面板中的 AddComponent &#xff0c;输入“VideoPlayer”。 资源 这里 视频资源有两种形式&#xff0c;第一种是 VideoClip &#xff0c;需要将视频文件拖拽到该属性字段…...

RSTP环路避免实验(华为)

思科设备参考&#xff1a;RSTP环路避免实验&#xff08;思科&#xff09; 一&#xff0c;技术简介 RSTP (Rapid Spanning Tree Protocol) 是从STP发展而来 • RSTP标准版本为IEEE802.1w • RSTP具备STP的所有功能&#xff0c;可以兼容STP运行 • RSTP和STP有所不同 减少了…...

Arduino IDE工程代码多文件编程和中文设置

一、esp8266模块信息 二、中英文切换 点击文件( File )–选择首选项( Preference )—选择语言( Language )—选择中文–点击确定( OK ) 三、多文件编程 在Arduino编程中&#xff0c;将代码分割成多个文件是一种很好的做法&#xff0c;特别是项目变得越来越大和复杂时。这样…...

【微服务】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设置代理一般来说很简单&#xff0c;对于无密码或者可以支持密钥登录的&#xff0c;都比较无脑 难的地方在于使用用户名密码认证来使用一个http的代理或者socks5的代理&#xff0c;密码如何设置&#xff1f;特殊字符如何处理&#xff1f; 直接上答案&#xff0c;.ssh/conf…...

C++ union用法

在C中&#xff0c;union是一种特殊的数据类型&#xff0c;可以在同一个内存位置存储不同的数据类型。它的用法如下&#xff1a; 1. 声明union类型&#xff1a;使用关键字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实现熔断与限流

注&#xff1a;本篇文章主要参考周阳老师讲解的cloud进行整理的&#xff01; 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发行版中都是可用的&#xff0c;包括但不限于Debian、Ubuntu、Alpine、Arch Linux、Kali Linux、R…...

数据结构——顺序表(C语言版)

顺序表是数据结构中最基本的一种线性表&#xff0c;它以一段连续的存储空间来存储数据元素&#xff0c;元素之间的顺序由它们在内存中的位置来决定。在C语言中&#xff0c;我们通常使用数组来实现顺序表。 目录 顺序表的结构定义 顺序表的基本操作 应用实例 顺序表的结构定义…...

Knative 助力 XTransfer 加速应用云原生 Serverless 化

作者&#xff1a;元毅 公司介绍 XTransfer 是一站式外贸企业跨境金融和风控服务公司&#xff0c;致力于帮助中小微企业大幅降低全球展业的门槛和成本&#xff0c;提升全球竞争力。公司连续7年专注 B2B 外贸金融服务&#xff0c;已成为中国 B2B 外贸金融第一平台&#xff0c;目…...

服务器离线配置vscode连接,conda虚拟环境

记录一下服务器离线配置问题&#xff0c;以备不时之需。 服务器离线配置 vscode连接参考&#xff1a;vscode-server离线安装-CSDN博客 服务器离线配置conda虚拟环境&#xff1a;Conda 环境离线迁移&#xff08;服务器断网情况下搭建虚拟环境envs&#xff09; - 知乎 上次两个…...

各种需要使用的方法-->vue/微信小程序/layui

各种需要使用的方法-->vue/微信小程序/layui 1、vue里样式不起作用的方法&#xff0c;可以通过deep穿透的方式2、 js获取本周、上周、本月、上月日期3、ArrayBuffer Blob 格式转换ArrayBuffer与Blob的区别ArrayBuffer转BlobBlob转ArrayBuffer需要借助fileReader对象 4、使用…...

360奇酷刷机 360刷机助手 QGDP360手机QGDP刷机

360奇酷刷机 360刷机助手 QGDP破解版360手机QGDP刷机 360手机刷机资源下载链接&#xff1a;360rom.github.io 参考&#xff1a;360手机-360刷机360刷机包twrp、root 360奇酷刷机&#xff1a;360高通驱动安装 360手机刷机驱动&#xff1b;手机内置&#xff0c;可通过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简单合批

思路&#xff1a; CPU和GPU都开辟同样大小的一大块内存&#xff08;为了存储顶点信息&#xff09; 索引在程序运行时生成对应规则后绑定到索引缓冲中 动态生成顶点信息&#xff08;现在改成Drawquad只是确定图形顶点的位置&#xff09; 然后在Endscene&#xff0c;将CPU的动…...

粘包/半包及解决方案

一、粘包/半包介绍 1&#xff1a;粘包 粘包&#xff08;Packet Concatenation&#xff09;通常发生在基于流式传输协议&#xff08;如 TCP&#xff09;的通信中&#xff0c;因为 TCP 是面向流的传输协议&#xff0c;它不保证数据包的边界&#xff0c;而是将数据视为连续的字节…...

2024华为软件精英挑战赛记录

前言 本次主要是记录自己第一次参加华为软件挑战赛的经历。第一次参加比赛还是缺少经验&#xff0c;训练赛中拿到赛区的20多名&#xff0c;最后在正式赛中被反超了&#xff0c;只拿了40多名&#xff0c;实在是感到可惜。 题目&#xff1a;本次题目是一个智慧港口的问题。10个机…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

Keil 中设置 STM32 Flash 和 RAM 地址详解

文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

搭建DNS域名解析服务器(正向解析资源文件)

正向解析资源文件 1&#xff09;准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2&#xff09;服务端安装软件&#xff1a;bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...

根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的----NTFS源代码分析--重要

根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的 第一部分&#xff1a; 0: kd> g Breakpoint 9 hit Ntfs!ReadIndexBuffer: f7173886 55 push ebp 0: kd> kc # 00 Ntfs!ReadIndexBuffer 01 Ntfs!FindFirstIndexEntry 02 Ntfs!NtfsUpda…...

Chrome 浏览器前端与客户端双向通信实战

Chrome 前端&#xff08;即页面 JS / Web UI&#xff09;与客户端&#xff08;C 后端&#xff09;的交互机制&#xff0c;是 Chromium 架构中非常核心的一环。下面我将按常见场景&#xff0c;从通道、流程、技术栈几个角度做一套完整的分析&#xff0c;特别适合你这种在分析和改…...

macOS 终端智能代理检测

&#x1f9e0; 终端智能代理检测&#xff1a;自动判断是否需要设置代理访问 GitHub 在开发中&#xff0c;使用 GitHub 是非常常见的需求。但有时候我们会发现某些命令失败、插件无法更新&#xff0c;例如&#xff1a; fatal: unable to access https://github.com/ohmyzsh/oh…...