Leetcode 3363. Find the Maximum Number of Fruits Collected
- Leetcode 3363. Find the Maximum Number of Fruits Collected
- 1. 解题思路
- 2. 代码实现
- 题目链接:3363. Find the Maximum Number of Fruits Collected
1. 解题思路
这一题是一道陷阱题……
乍一眼看过去,由于三人的路线完全可能重叠,因此需要考虑路线当中果子是否有被取走的情况,就会变得异常复杂,完全想不到解答的思路。
但是后续仔细一看题目,要求三人都必须在 n − 1 n-1 n−1步之后走到点 ( n − 1 , n − 1 ) (n-1, n-1) (n−1,n−1),因此这道题就被大大简化了,因为:
- 对于第一个孩子而言,虽然可走的路线非常多,但是要求 n − 1 n-1 n−1步之后走到点 ( n − 1 , n − 1 ) (n-1, n-1) (n−1,n−1),他能走的路线事实上也就是沿着对角线的最短路线了;
- 对于第二个孩子,由于终点必须走到点 ( n − 1 , n − 1 ) (n-1, n-1) (n−1,n−1),因此事实上他最远能走到的位置也就是对角线的位置,而由于对角线上的果子必然都被第一个孩子拿走了,因此他事实上只会在对角线的上方行走,只有在最后一步会走到 ( n − 1 , n − 1 ) (n-1, n-1) (n−1,n−1)。
- 同样对于第三个孩子,出于同样的限制条件,他事实上也只会在对角线下方行走,且最后一步会走到 ( n − 1 , n − 1 ) (n-1, n-1) (n−1,n−1)。
因此,事实上三人的路线是完全不会重合的,或者说最优方案中三人的路线必然不重合,因此我们只需要分别独立考察第二和第三个孩子的最优路线即可,而这就是两个简单的动态规划的问题了。
2. 代码实现
给出python代码实现如下:
class Solution:def maxCollectedFruits(self, fruits: List[List[int]]) -> int:n = len(fruits)s1 = sum(fruits[i][i] for i in range(n))@lru_cache(None)def dp1(i, j):if i == n-2 and j == n-1:return fruits[i][j]ans = -math.inffor k in range(j-1, j+2):if k < n and k > i:ans = max(ans, fruits[i][j] + dp1(i+1, k))return ans@lru_cache(None)def dp2(i, j):if i == n-1 and j == n-2:return fruits[i][j]ans = -math.inffor k in range(i-1, i+2):if k < n and k > j:ans = max(ans, fruits[i][j] + dp2(k, j+1))return ansreturn s1 + dp1(0, n-1) + dp2(n-1, 0)
提交代码评测得到:耗时1946ms,占用内存297.3MB。
相关文章:
Leetcode 3363. Find the Maximum Number of Fruits Collected
Leetcode 3363. Find the Maximum Number of Fruits Collected 1. 解题思路2. 代码实现 题目链接:3363. Find the Maximum Number of Fruits Collected 1. 解题思路 这一题是一道陷阱题…… 乍一眼看过去,由于三人的路线完全可能重叠,因此…...
【数据仓库 | Data Warehouse】数据仓库的四大特性
1. 前言 数据仓库是用于支持管理和决策的数据集合,它汇集了来自不同数据源的历史数据,以便进行多维度的分析和报告。数据仓库的四大特点是:主题性,集成性,稳定性,时变性。 2. 主题性(Subject-Oriented) …...
springboot配置多数据源mysql+TDengine保姆级教程
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、pom文件二、yamlDataSourceConfigServiceMapper.xml测试总结 前言 Mybatis-plus管理多数据源,数据库为mysql和TDengine。 一、pom文件 <de…...
dns实验2:反向解析
启动服务: 给虚拟机网卡添加IP地址: 查看有几个IP地址: 打开配置文件: 重启服务,该宽松模式,关闭防火墙: 本机测试: windows测试:(本地shell)...
ZooKeeper 基础知识总结
先赞后看,Java进阶一大半 ZooKeeper 官网这样介绍道:ZooKeeper 是一种集中式服务,用于维护配置信息、命名、提供分布式同步和提供组服务。 各位hao,我是南哥,相信对你通关面试、拿下Offer有所帮助。 ⭐⭐⭐一份南哥编写…...
npm库xss依赖的使用方法和vue3 中Web富文本编辑器 wangeditor 使用xss库解决 XSS 攻击的方法
npm库xss依赖的使用方法和vue3 中Web富文本编辑器 wangeditor 使用xss库解决 XSS 攻击的方法 1. npm库xss依赖的使用方法1.1 xss库定义1.2 xss库功能 2. vue3 中 wangeditor 使用xss库解决 XSS 攻击的方法和示例2.1 在终端执行如下命令安装 xss 依赖2.2 在使用 wangeditor 的地…...
微信小程序蓝牙writeBLECharacteristicValue写入数据返回成功后,实际硬件内信息查询未存储?
问题:连接蓝牙后,调用小程序writeBLECharacteristicValue,返回传输数据成功,查询硬件响应发现没有存储进去? 解决:一直以为是这个write方法的问题,找了很多相关贴,后续进行硬件日志…...
5G NR:带宽与采样率的计算
100M 带宽是122.88Mhz sampling rate这是我们都知道的,那它是怎么来的呢? 采样率 子载波间隔 * 采样长度 38.211中对于Tc的定义, 在LTE是定义了Ts,在NR也就是5G定义了Tc。 定义这个单位会对我们以后工作中的计算至关重要。 就是在…...
go 和java 编写方式的理解
1. go 推荐写流水账式的代码(非贬义),自己管自己。java喜欢封装各种接口供外部调用,让别人来管自己。 2. 因为协程的存在, go的变量作用域聚集在方法内部,即函数不可重入,而java线程的限制&…...
C# 7.1 .Net Framwork4.7 VS2017环境下,方法的引用与调用
方法的调用比较好理解,就是给方法传递实参,执行方法代码。 方法引用涉及委托,委托签名与其引用的方法必须一致。以下demo说明方法调用与引用在写程序时的区别: using System; using System.Collections.Generic; using System.L…...
etcd、kube-apiserver、kube-controller-manager和kube-scheduler有什么区别
在我们部署K8S集群的时候 初始化master节点之后(在master上面执行这条初始化命令) kubeadm init --apiserver-advertise-address10.0.1.176 --image-repository registry.aliyuncs.com/google_containers --kubernetes-version v1.16.0 --service…...
每日一题 LCR 057. 存在重复元素 III
LCR 057. 存在重复元素 III 滑动窗口二分查找 有序集合 有lower_bound(num) ,可以找到第一个大于其的数字 class Solution { public:bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {set<long> win;for(int i0;i<nums.size();i){a…...
使用IDEA编写测试用例,复杂度校验
最近我们公司要求开发人员必须写测试用例,组织了TDD培训,测试驱动开发,同时衡量代码的圈复杂度,我记录下初次使用的过程。 编写测试用例,查看用例覆盖度 1、要编写测试用例,并看下测试用例的覆盖度&#…...
搭建私有云存储
1、安装LNMP环境 yum install nginx -y yum install -y nginx mariadb-server php php-fpm php-mysqlnd systemctl restart nginx.service --- 启动Nginx systemctl start mariadb.service ---启动数据库 mysql -e create database lxdb character set utf8 ---创建数据库 my…...
【从零开始的LeetCode-算法】3304. 找出第 K 个字符 I
Alice 和 Bob 正在玩一个游戏。最初,Alice 有一个字符串 word "a"。 给定一个正整数 k。 现在 Bob 会要求 Alice 执行以下操作 无限次 : 将 word 中的每个字符 更改 为英文字母表中的 下一个 字符来生成一个新字符串,并将其 追加 到原始的…...
深入解析分布式遗传算法及其Python实现
目录 深入解析分布式遗传算法及其Python实现目录第一部分:分布式遗传算法的背景与原理1.1 遗传算法概述1.2 分布式遗传算法的引入1.3 分布式遗传算法的优点与挑战优点:挑战:第二部分:分布式遗传算法的通用Python实现2.1 基本组件的实现第三部分:案例1 - 基于多种交叉与变异…...
gitee:创建仓库,存入本地文件至仓库
一、git下载 git:下载与安装-CSDN博客https://blog.csdn.net/weixin_46001736/article/details/144107485?sharetypeblogdetail&sharerId144107485&sharereferPC&sharesourceweixin_46001736&spm1011.2480.3001.8118 二、创建仓库 1、主页面->右上角新增…...
计算分数的浮点数值
计算分数的浮点数值 C语言代码C 代码Java代码Python代码 💐The Begin💐点点关注,收藏不迷路💐 两个整数a和b分别作为分子和分母,既分数 a/b ,求它的浮点数值(双精度浮点数,保留小数点…...
在 C/C++ 中,volatile 关键字的作用是什么?.volatile 关键字与 const 关键字有什么区别?
volatile关键字用于告诉编译器,被修饰的变量可能会被程序以外的因素(如硬件、操作系统等)修改,因此每次访问该变量时都应该从内从中读取他的值,而不是使用可能存在的缓存之,这在多线程编程,与硬…...
golang debug调试
1. 本地调试 1:Add Configurations 添加配置文件(Run kind :Directory) 2:进入run运行窗口 3:debug断点调试模式 1. Resume Program (继续运行) 图标: ▶️ 或 ► 快捷键: F9(Windows/Linux&a…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...
【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】
1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件(System Property Definition File),用于声明和管理 Bluetooth 模块相…...
Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)
引言:为什么 Eureka 依然是存量系统的核心? 尽管 Nacos 等新注册中心崛起,但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制,是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...
Robots.txt 文件
什么是robots.txt? robots.txt 是一个位于网站根目录下的文本文件(如:https://example.com/robots.txt),它用于指导网络爬虫(如搜索引擎的蜘蛛程序)如何抓取该网站的内容。这个文件遵循 Robots…...
听写流程自动化实践,轻量级教育辅助
随着智能教育工具的发展,越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式,也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建,…...
中医有效性探讨
文章目录 西医是如何发展到以生物化学为药理基础的现代医学?传统医学奠基期(远古 - 17 世纪)近代医学转型期(17 世纪 - 19 世纪末)现代医学成熟期(20世纪至今) 中医的源远流长和一脉相承远古至…...
GruntJS-前端自动化任务运行器从入门到实战
Grunt 完全指南:从入门到实战 一、Grunt 是什么? Grunt是一个基于 Node.js 的前端自动化任务运行器,主要用于自动化执行项目开发中重复性高的任务,例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...
深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用
文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么?1.1.2 感知机的工作原理 1.2 感知机的简单应用:基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...
基于IDIG-GAN的小样本电机轴承故障诊断
目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) 梯度归一化(Gradient Normalization) (2) 判别器梯度间隙正则化(Discriminator Gradient Gap Regularization) (3) 自注意力机制(Self-Attention) 3. 完整损失函数 二…...
tomcat指定使用的jdk版本
说明 有时候需要对tomcat配置指定的jdk版本号,此时,我们可以通过以下方式进行配置 设置方式 找到tomcat的bin目录中的setclasspath.bat。如果是linux系统则是setclasspath.sh set JAVA_HOMEC:\Program Files\Java\jdk8 set JRE_HOMEC:\Program Files…...
