力扣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…...
MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例
一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...
python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)
更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...
EtherNet/IP转DeviceNet协议网关详解
一,设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络,本网关连接到EtherNet/IP总线中做为从站使用,连接到DeviceNet总线中做为从站使用。 在自动…...
深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...
JAVA后端开发——多租户
数据隔离是多租户系统中的核心概念,确保一个租户(在这个系统中可能是一个公司或一个独立的客户)的数据对其他租户是不可见的。在 RuoYi 框架(您当前项目所使用的基础框架)中,这通常是通过在数据表中增加一个…...
处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的
修改bug思路: 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑:async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...
云原生安全实战:API网关Kong的鉴权与限流详解
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关(API Gateway) API网关是微服务架构中的核心组件,负责统一管理所有API的流量入口。它像一座…...
Windows安装Miniconda
一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...
解决:Android studio 编译后报错\app\src\main\cpp\CMakeLists.txt‘ to exist
现象: android studio报错: [CXX1409] D:\GitLab\xxxxx\app.cxx\Debug\3f3w4y1i\arm64-v8a\android_gradle_build.json : expected buildFiles file ‘D:\GitLab\xxxxx\app\src\main\cpp\CMakeLists.txt’ to exist 解决: 不要动CMakeLists.…...
Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)
引言 工欲善其事,必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后,我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集,就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...

