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

LeetCode 每日一题 ---- 【741.摘樱桃】

LeetCode 每日一题 ---- 【741.摘樱桃】

  • 741.摘樱桃
    • 方法:动态规划

741.摘樱桃

方法:动态规划

这是一道动态规划的题目,enmmmm,依旧是做不出来,尤其是看到困难两个标红的字体,就更不想做了,然后是看着答案一点一点顺着思路和题解做的,做完后发现也没有想象中的那么难

从(n-1, n-1)返回(0, 0)可以等价的看做又一次从(0, 0)到(n-1, n-1)的路径,
然后求一个所能采到樱桃个数的最大值
不妨假设两人同时出发,且速度相同。无论这两人怎么走,在时间相同的情况下,
他们向右走的步数加上向下走的步数之和是一个定值(设为 k)。
设两人的坐标为 (x1,y1)和 (x2,y2),则 x1+y1=x2+y2=k。
那么当 x1=x2 时,必然有 y1=y2,即两个人到达了同一个格子。
定义状态:f[k][x1][x2]
k表示两个人分别从(x1, k - x1)和(x2, k - x2)同时触发,到达(n-1, n-1)锁摘到樱桃个数之和
x1,x2分别代表第一个和第二个人的起始横坐标
状态转移方程:
f[k][x1][x2]可以由四种情况转移过来
都往右:f[k][x1][x2] = f[k-1][x1][x2]
A往下,B往右:f[k][x1][x2] = f[k-1][x1-2][x2]
A往右,B往下:f[k][x1][x2] = f[k-1][x1][x2-1]
都往下:f[k][x1][x2] = f[k-1][x1-1][x2-1]
f[k][x1][x2]的最终结果是上述四种情况的最大值,然后再累加上grid[x1][k-x1]和grid[x2][k-x2]就可以得到最终该位置的答案
若x1==x2说明第一个人和第二个人的位置重合了,所以在这种情况下,grid[x1][k-x1]只能加一次

/**
从(n-1, n-1)返回(0, 0)可以等价的看做又一次从(0, 0)到(n-1, n-1)的路径,
然后求一个所能采到樱桃个数的最大值
不妨假设两人同时出发,且速度相同。无论这两人怎么走,在时间相同的情况下,
他们向右走的步数加上向下走的步数之和是一个定值(设为 k)。
设两人的坐标为 (x1,y1)和 (x2,y2),则 x1+y1=x2+y2=k。
那么当 x1=x2 时,必然有 y1=y2,即两个人到达了同一个格子。
定义状态:f[k][x1][x2] k表示两个人分别从(x1, k - x1)和(x2, k - x2)同时触发,到达(n-1, n-1)锁摘到樱桃个数之和x1,x2分别代表第一个和第二个人的起始横坐标
状态转移方程:f[k][x1][x2]可以由四种情况转移过来都往右:f[k][x1][x2] = f[k-1][x1][x2]A往下,B往右:f[k][x1][x2] = f[k-1][x1-2][x2]A往右,B往下:f[k][x1][x2] = f[k-1][x1][x2-1]都往下:f[k][x1][x2] = f[k-1][x1-1][x2-1]f[k][x1][x2]的最终结果是上述四种情况的最大值,然后再累加上grid[x1][k-x1]和grid[x2][k-x2]就可以得到最终该位置的答案若x1==x2说明第一个人和第二个人的位置重合了,所以在这种情况下,grid[x1][k-x1]只能加一次*/
class Solution {public int cherryPickup(int[][] grid) {int n = grid.length;int[][][] f = new int[n * 2 - 1][n][n];// 初始化for (int i = 0; i < n * 2 - 1; i ++ ) {for (int j = 0; j < n; j ++ ) {Arrays.fill(f[i][j], Integer.MIN_VALUE);}}f[0][0][0] = grid[0][0];for (int k = 1; k < n * 2 - 1; k ++ ) {// 防止越界for (int x1 = Math.max(k - n + 1, 0); x1 <= Math.min(k, n - 1); x1 ++ ) {int y1 = k - x1;// 荆棘不可越过if (grid[x1][y1] == -1) {continue;}for (int x2 = x1; x2 <= Math.min(k, n - 1); x2 ++ ) {int y2 = k - x2;if (grid[x2][y2] == -1) {continue;}// 都往右int res = f[k - 1][x1][x2];// 往下,往右if (x1 > 0) {res = Math.max(res, f[k - 1][x1 - 1][x2]);}// 往右,往下if (x2 > 0) {res = Math.max(res, f[k - 1][x1][x2 - 1]);}// 都往下if (x1 > 0 && x2 > 0) {res = Math.max(res, f[k - 1][x1 - 1][x2 - 1]);}res += grid[x1][y1];if (x2 != x1) {res += grid[x2][y2];}f[k][x1][x2] = res;}}}return Math.max(f[n * 2 - 2][n - 1][n - 1], 0);}
}

时间复杂度:
O(n3)

空间复杂度:
O(n2)

相关文章:

LeetCode 每日一题 ---- 【741.摘樱桃】

LeetCode 每日一题 ---- 【741.摘樱桃】 741.摘樱桃方法&#xff1a;动态规划 741.摘樱桃 方法&#xff1a;动态规划 这是一道动态规划的题目&#xff0c;enmmmm&#xff0c;依旧是做不出来&#xff0c;尤其是看到困难两个标红的字体&#xff0c;就更不想做了&#xff0c;然后…...

新火种AI|挑战谷歌,OpenAI要推出搜索引擎?

作者&#xff1a;一号 编辑&#xff1a;美美 在AI革新的浪潮下&#xff0c;谷歌搜索迎来了越来越多的“挑战者”。 最近&#xff0c;据多家外媒的消息&#xff0c;有知情人士透露&#xff0c;OpenAI正计划上线一款基于ChatGPT的大型产品&#xff0c;将提供一个新的搜索引擎&…...

选择适用的无尘棉签:保障洁净生产环境下的高效擦拭

随着洁净生产条件的日益普及和无尘级别要求的提高&#xff0c;无尘擦拭用品成为广大用户追捧的必备工具。在这个领域&#xff0c;无尘棉签作为一种高效的擦拭工具&#xff0c;扮演着重要的角色。然而&#xff0c;面对市场上种类繁多的无尘棉签&#xff0c;如何选择最合适的产品…...

通信录的动态版本

一. 增加需求 在学习了动态开辟内存之后 我们对于通讯录产生了新的需求 要求我们做出一个动态增长的版本 即 随着我们储存联系人的增加 储存的空间增加 要求 &#xff1a; 1 初始空间为3 2 每次达到上限之后 扩容两个内存 二. 动手实施 我们首先要创建一个结构体 结构体…...

FineReport高频面试题及参考答案

FineReport是一款利用什么语言开发的报表工具&#xff1f; FineReport是一款基于Java语言开发的报表工具。Java是一种广泛使用的编程语言&#xff0c;特别适合于跨平台的软件开发。FineReport利用Java语言的诸多优势&#xff0c;如稳定性、安全性、可移植性和强大的网络功能&a…...

git merge 命令合并指定分支到当前分支

git merge 是一个用于合并两个分支的 Git 命令。当你在不同的分支上工作时&#xff0c;可能会有一些不同的更改。使用 git merge 可以将这些更改合并到一起。以下是一些常见的 git merge 用法示例&#xff1a; 1. 合并当前分支与另一个分支的更改 git merge <branch-name&…...

【在线OJ】Vue创建OJ管理系统

一、创建项目 vue ui命令创建项目 项目创建完成后来到项目 二、导航栏 首先创建一个根页面&#xff0c;让他展示在页面上 创建之后来到路由配置界面 然后安装ElementUI&#xff0c;来到官网找到导航栏 复制代码后粘贴到刚才创建的vue文件里&#xff0c;启动项目&#xff…...

常用算法汇总

作者&#xff1a;指针不指南吗 专栏&#xff1a;算法篇 &#x1f43e;算法思维逻辑&#x1f43e; 文章目录 1.判断闰年2.计算从某天到某天的天数3.二分4. 前缀和5.差分6.图论6.1dfs6.2走迷宫 7.最短路7.1dijkstra7.2foly 8.并查集9.数论9.1gcd lcm9.2判断素数(质数)9.3分解质因…...

W801学习笔记二十二:英语背单词学习应用——下

续上篇&#xff1a; W801学习笔记二十一&#xff1a;英语背单词学习应用——上 五、处理用户交互 由于英语也是采用了和唐诗一样的《三分钟限时挑战》《五十题竞速挑战》《零错误闯关挑战》&#xff0c;所以用户交互的逻辑和唐诗是一样的。所以&#xff0c;我们抽一个基类&a…...

Vue路由的模式和原理

一、hash模式&#xff08;默认&#xff09; 使用URL的hash来模拟一个完整的URL&#xff0c;当URL发生改变时不会向服务器发起请求。# 和其后面的字符称为hash&#xff0c;可通过 window.location.hash 获取。当hash改变会触发&#xff08;包括浏览器的前进、后退&#xff09;会…...

在K8S中,静态、动态、自主式Pod有何区别

在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;静态Pod、自主式Pod和动态Pod是不同管理方式下的Pod类型&#xff0c;它们的区别主要体现在创建和管理方式上&#xff1a; 静态Pod&#xff1a; 静态Pod是由kubelet直接管理的&#xff0c;其配置文件存储在节点本地而…...

【Three.js基础学习】15.scroll-based-animation

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 前言 课程要点 结合html等场景 做滚动动画 1.遇到的问题&#xff0c; 在向下滚动时&#xff0c;下方会显白&#xff08;部分浏览器&#xff09; 解决&#xff1a;alpha:true …...

ubantu安装mysql

安装 准备&#xff1a;下载&#xff1a;版本5.1.17的MySQL并上传至Ubuntu系统 #解压 tar -xvf mysql-server_5.7.17-1ubuntu16.10_amd64.deb-bundle.tar #提前安装插件 sudo apt-get install libaio1 libmecab2 #若安装失败使用以下命令 apt --fix-broken install sudo apt-g…...

注意!华为HCIP-Datacom认证考试题有变化!

01 注意 HCIP Datacom H12-831考试变题了&#xff0c;最近要考试的多观望一下&#xff0c;821目前稳定。 华为HCIP考试以后要加难度&#xff0c;增加实验题&#xff0c;还没考完的小伙伴抓紧时间了。 02 华为HCIP认证大更新 未来将增加实验考试&#xff0c;拒绝背题库的Pass&a…...

你是我的荣耀 | 林先生:从酷爱数学到毕业走向数据分析岗位

人物背景&#xff1a; 研究生国家奖学金、本科生国家奖学金、学业奖学金一等奖、上海市优秀毕业生&#xff1b; 应用统计专业 CPDA优秀学员 ## 为什么选择数据分析相关专业 我是应用统计专业的一个应届毕业生&#xff0c;目前在一家上海市属的国企&#xff0c;从事数据分析相关…...

操作系统真象还原-bochs安装

今天读了《操作系统真象还原》这本书&#xff0c;写上比较幽默通俗。书中例子需要安装一个bochs系统&#xff0c;记录一下安装过程。参考了书中1.4&#xff0c;1.5两节&#xff0c;书中尽让有两处问题&#xff0c;也记录了下来。 1.3 操作系统的宿主环境 下载地址&#xff1a…...

windows平台安装labelme

之前写过一篇文章也是关于在windows平台安装labelme的&#xff1a;《windows平台python版labelme安装与使用_labelme下载-CSDN博客》&#xff0c;随着软件与工具的更新换代&#xff0c;按照同样的方法最近在使用的时候出现了错误&#xff0c;出现创建虚拟环境失败&#xff0c;具…...

微服务之SpringCloud AlibabaSeata处理分布式事务

一、概述 1.1背景 一次业务操作需要跨多个数据源或需要跨多个系统进行远程调用&#xff0c;就会产生分布式事务问题 but 关系型数据库提供的能力是基于单机事务的&#xff0c;一旦遇到分布式事务场景&#xff0c;就需要通过更多其他技术手段来解决问题。 全局事务&#xff1a;…...

2005-2021年全国各地级市生态环境注意力/环保注意力数据(根据政府报告文本词频统计)

2005-2021年全国各地级市生态环境注意力/环保注意力数据&#xff08;根据政府报告文本词频统计&#xff09; 2005-2021年全国各地级市生态环境注意力/环保注意力数据&#xff08;根据政府报告文本词频统计&#xff09; 1、时间&#xff1a;2005-2021年 2、范围&#xff1a;2…...

熟悉这些道理可以让人更好地应对各种挑战和困难。

1. 为别人尽最大的力量&#xff0c;最后就是为自己尽最大的力量。——罗斯金 2. 世上有一条永恒不变的法则:当你不在乎&#xff0c;你就得到。当你变好&#xff0c;你才会遇到更好的。只有当你变强大&#xff0c;你才不害怕孤单。当你不害怕孤单&#xff0c;你才能够宁缺毋滥。…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

Cesium1.95中高性能加载1500个点

一、基本方式&#xff1a; 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

MySQL用户和授权

开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务&#xff1a; test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...

Typeerror: cannot read properties of undefined (reading ‘XXX‘)

最近需要在离线机器上运行软件&#xff0c;所以得把软件用docker打包起来&#xff0c;大部分功能都没问题&#xff0c;出了一个奇怪的事情。同样的代码&#xff0c;在本机上用vscode可以运行起来&#xff0c;但是打包之后在docker里出现了问题。使用的是dialog组件&#xff0c;…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...