力扣LCR 166. 珠宝的最高价值(java 动态规划)
Problem: LCR 166. 珠宝的最高价值
文章目录
- 解题思路
- 思路
- 解题方法
- 复杂度
- Code
解题思路
思路
改题目与本站64题实质上是一样的,该题目在64题的基础上将求取最小路径和改成了求取最大路径和。具体实现思路如下:
1.定义一个int类型的二维数组dp大小为给定矩阵frame的行数与列数。该数组用于记录每个当前阶段的最大路径和(也是本题目的最大价值)
2.动态转移方程为**dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + frame[i][j];**即当前位置(也可以记作阶段)最大值每次取出其上方,和左侧的较大值的一个与当前frame位置值作和;
3.由于dp数组中第一行与第一列无法直接执行动态转移方程,要对其初始化:第一行每个位置值为依次向右累加;第一列每个位置值为依次向下累加
3.最后返回dp数组中的最后一个值即可。
解题方法
1.定义数组frame的行数rows与列数columns;并定义一个int变量temp用于记录累加和
2.定义并初始化int类型数组dp初始化为new int[rows][colunms]
3.初始化dp的第一行与第一列,在for循环中使temp依次累加当前第一行(列)位置的值,并赋值给当前dp数组位置;
4.从dp数组的第二行(索引为1)开始执行动态转移方程dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + frame[i][j];,最后返回dp[rows - 1][columns - 1];
复杂度
时间复杂度:
O ( M N ) O(MN) O(MN),其中 M M M为数组frame的行数, N N N为其列数
空间复杂度:
O ( M N ) O(MN) O(MN)
Code
class Solution {/*** The maximum path sum is obtained using dynamic programming** @param frame Given matrix* @return int*/public int jewelleryValue(int[][] frame) {int rows = frame.length;int columns = frame[0].length;int temp = 0;//Records the current maximum path sumint[][] dp = new int[rows][columns];//Handle the first row and columnfor (int i = 0; i < columns; ++i) {temp += frame[0][i];dp[0][i] = temp;}temp = 0;for (int j = 0; j < rows; ++j) {temp += frame[j][0];dp[j][0] = temp;}//Dynamic transfer equationfor (int i = 1; i < rows; ++i) {for (int j = 1; j < columns; ++j) {dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + frame[i][j];}}return dp[rows - 1][columns - 1];}
}
相关文章:
力扣LCR 166. 珠宝的最高价值(java 动态规划)
Problem: LCR 166. 珠宝的最高价值 文章目录 解题思路思路解题方法复杂度Code 解题思路 思路 改题目与本站64题实质上是一样的,该题目在64题的基础上将求取最小路径和改成了求取最大路径和。具体实现思路如下: 1.定义一个int类型的二维数组dp大小为给定…...
【Python基础】一文搞懂:Python 中 Excel 文件的写入与读取
文章目录 1 引言2 使用 openpyxl2.1 安装 openpyxl2.2 写入 Excel 文件2.3 读取 Excel 文件 3 使用 pandas3.1 安装 pandas 和 openpyxl3.2 写入 Excel 文件3.3 读取 Excel 文件 4 实例演示4.1 安装所需库4.2 封装为excel_example.py脚本文件 5 注意事项6 总结 1 引言 在现代办…...
二叉树题目:完全二叉树插入器
文章目录 题目标题和出处难度题目描述要求示例数据范围 解法思路和算法代码复杂度分析 题目 标题和出处 标题:完全二叉树插入器 出处:919. 完全二叉树插入器 难度 6 级 题目描述 要求 完全二叉树是每一层(除最后一层外)都…...
用MATLAB求最短路径(graphshortestpath)和求最小生成树(minspantree),代码演示
求最短路径(graphshortestpath),求最小生成树(minspantree) 文章目录 求最短路径(graphshortestpath),求最小生成树(minspantree)1、最短路径问题2、最小生成…...
用win系统搭建Minecraft世界服务器,MC开服教程,小白开服教程
雨云VPS用Windows系统搭建我的世界世界服务器,Minecraft开服教程,小白开服教程,MC 1.19.4版本服务器搭建教程。 此教程使用 Mohist 1.19.4 服务端,此服务端支持Forge模组和Bukkit/Spigot/Paper插件,如果需要开其他服务…...
MacOS安装Miniforge、Tensorflow、Jupyter Lab等(2024年最新)
大家好,我是邵奈一,一个不务正业的程序猿、正儿八经的斜杠青年。 1、世人称我为:被代码耽误的诗人、没天赋的书法家、五音不全的歌手、专业跑龙套演员、不合格的运动员… 2、这几年,我整理了很多IT技术相关的教程给大家࿰…...
iOS 应用上架指南:资料填写及提交审核
摘要 本文提供了iOS新站上架资料填写及提交审核的详细指南,包括创建应用、资料填写-综合、资料填写-IOS App和提交审核等步骤。通过本指南,您将了解到如何填写正确的资料,并顺利通过苹果公司的审核。 引言 在开发iOS应用后,将其…...
车速预测 | Matlab基于RBF径向基神经网络的车速预测模型(多步预测,尾巴图)
目录 效果一览基本介绍程序设计参考资料 效果一览 基本介绍 车速预测 | Matlab基于RBF径向基神经网络的车速预测模型(多步预测,尾巴图) 程序设计 完整程序和数据获取方式:私信博主回复Matlab基于RBF径向基神经网络的车速预测模型…...
MySQL 5.7.35下载安装使用_忘记密码_远程授权
文章目录 MySQL 5.7.35下载安装使用_忘记密码_远程授权MySQL下载地址mysql安装点击安装,最好以管理员身份运行选择自定义安装选择64位勾选启动自定义产品执行点击同意点击下一步点击执行下一步配置数据库端口号设置登录密码,如果密码忘记,下面…...
openGauss学习笔记-194 openGauss 数据库运维-常见故障定位案例-分析查询语句长时间运行的问题
文章目录 openGauss学习笔记-194 openGauss 数据库运维-常见故障定位案例-分析查询语句长时间运行的问题194.1 分析查询语句长时间运行的问题194.1.1 问题现象194.1.2 原因分析194.1.3 处理办法 openGauss学习笔记-194 openGauss 数据库运维-常见故障定位案例-分析查询语句长时…...
GoLang:gRPC协议的介绍以及详细教程,从Protocol开始
目录 编辑 引言 一、安装相关Go语言库和相关工具 1. 安装Go 2. 安装Protocol Buffers Compiler 2.1 Windows 2.1.1 下载 2.1.2 解压 2.1.3 环境变量 2. macOS 3. Linux 4. 验证安装 3. 安装gRPC-Go 4. 安装Protocol Buffers的Go插件 二、定义服务 三、生成Go…...
LeetCode-2645. 构造有效字符串的最少插入数
给你一个字符串 word ,你可以向其中任何位置插入 “a”、“b” 或 “c” 任意次,返回使 word 有效需要插入的最少字母数。 如果字符串可以由 “abc” 串联多次得到,则认为该字符串有效 。 示例 1: 输入:word “b” …...
ssm+vue的城投公司企业人事管理系统设计与实现(有报告)。Javaee项目,ssm vue前后端分离项目。
演示视频: ssmvue的城投公司企业人事管理系统设计与实现(有报告)。Javaee项目,ssm vue前后端分离项目。 项目介绍: 采用M(model)V(view)C(controller&#x…...
nginx基础面试题以及配置文件解析和命令控制
目录 1、nginx是什么 2、nginx的特点 3、为什么中国大陆有:百度、京东、新浪、网易、腾讯、淘宝等这么多用户使用nginx 4、nginx 的内部技术架构 上一期我们配置安装了nginx接着讲一下nginx配置文件的解析和nginx 命令控制 感谢观看!希望能够帮助到…...
全自动网页生成系统网站源码重构版
源码优点: 所有模板经过精心审核与修改,完美兼容小屏手机大屏手机,以及各种平板端、电脑端和360浏览器、谷歌浏览器、火狐浏览器等等各大浏览器显示。 免费制作 为用户使用方便考虑,全自动网页制作系统无需繁琐的注册与登入,直…...
【算法每日一练]-动态规划 (保姆级教程 篇16) #纸带 #围栏木桩 #四柱河内塔
目录 今日知识点: 计算最长子序列的方案个数,类似最短路径个数问题 四柱河内塔问题:dp[i]min{ (p[i-k]f[k])dp[i-k] } 纸带 围栏木桩 四柱河内塔 纸带 思路: 我们先设置dp[i]表示从i到n的方案数。 那么减法操作中ÿ…...
Grounding 模型 + SAM 报错
引入 Grounding 目标检测模型串联 SAM 从而实现实例分割任务,目前支持 Grounding DINO 和 GLIP 参考教程 MMDetection-SAM 如果是 Grounding DINO 则安装如下依赖即可 cd playground pip install githttps://github.com/facebookresearch/segment-anything.git pip…...
linux 网络基础配置
将Linux主机接入到网络,需要配置网络相关设置一般包括如下内容: 主机名 iP/netmask (ip地址,网关) 路由:默认网关 网络连接状态 DNS服务器 (主DNS服务器 次DNS服务器 第三个DNS服务器) 一、…...
leetcode-相同的树
100. 相同的树 使用递归的方法 # Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution:def isSameTree(self, p: …...
Leetcode17-好数对的数目(1512)
1、题目 给你一个整数数组 nums 。 如果一组数字 (i,j) 满足 nums[i] nums[j] 且 i < j ,就可以认为这是一组 好数对 。 返回好数对的数目。 示例 1: 输入:nums [1,2,3,1,1,3] 输出:4 解释:有 4 组好数对&am…...
盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来
一、破局:PCB行业的时代之问 在数字经济蓬勃发展的浪潮中,PCB(印制电路板)作为 “电子产品之母”,其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透,PCB行业面临着前所未有的挑战与机遇。产品迭代…...
中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试
作者:Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位:中南大学地球科学与信息物理学院论文标题:BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接:https://arxiv.…...
Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...
[论文阅读]TrustRAG: Enhancing Robustness and Trustworthiness in RAG
TrustRAG: Enhancing Robustness and Trustworthiness in RAG [2501.00879] TrustRAG: Enhancing Robustness and Trustworthiness in Retrieval-Augmented Generation 代码:HuichiZhou/TrustRAG: Code for "TrustRAG: Enhancing Robustness and Trustworthin…...
Vue3中的computer和watch
computed的写法 在页面中 <div>{{ calcNumber }}</div>script中 写法1 常用 import { computed, ref } from vue; let price ref(100);const priceAdd () > { //函数方法 price 1price.value ; }//计算属性 let calcNumber computed(() > {return ${p…...
C# winform教程(二)----checkbox
一、作用 提供一个用户选择或者不选的状态,这是一个可以多选的控件。 二、属性 其实功能大差不差,除了特殊的几个外,与button基本相同,所有说几个独有的 checkbox属性 名称内容含义appearance控件外观可以变成按钮形状checkali…...
【Java多线程从青铜到王者】单例设计模式(八)
wait和sleep的区别 我们的wait也是提供了一个还有超时时间的版本,sleep也是可以指定时间的,也就是说时间一到就会解除阻塞,继续执行 wait和sleep都能被提前唤醒(虽然时间还没有到也可以提前唤醒),wait能被notify提前唤醒…...
Ray框架:分布式AI训练与调参实践
Ray框架:分布式AI训练与调参实践 系统化学习人工智能网站(收藏):https://www.captainbed.cn/flu 文章目录 Ray框架:分布式AI训练与调参实践摘要引言框架架构解析1. 核心组件设计2. 关键技术实现2.1 动态资源调度2.2 …...
7种分类数据编码技术详解:从原理到实战
在数据分析和机器学习领域,分类数据(Categorical Data)的处理是一个基础但至关重要的环节。分类数据指的是由有限数量的离散值组成的数据类型,如性别(男/女)、颜色(红/绿/蓝)或产品类…...
Q1起重机指挥理论备考要点分析
Q1起重机指挥理论备考要点分析 一、考试重点内容概述 Q1起重机指挥理论考试主要包含三大核心模块:安全技术知识(占40%)、指挥信号规范(占30%)和法规标准(占30%)。考试采用百分制,8…...

