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

力扣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题实质上是一样的&#xff0c;该题目在64题的基础上将求取最小路径和改成了求取最大路径和。具体实现思路如下&#xff1a; 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 引言 在现代办…...

二叉树题目:完全二叉树插入器

文章目录 题目标题和出处难度题目描述要求示例数据范围 解法思路和算法代码复杂度分析 题目 标题和出处 标题&#xff1a;完全二叉树插入器 出处&#xff1a;919. 完全二叉树插入器 难度 6 级 题目描述 要求 完全二叉树是每一层&#xff08;除最后一层外&#xff09;都…...

用MATLAB求最短路径(graphshortestpath)和求最小生成树(minspantree),代码演示

求最短路径&#xff08;graphshortestpath&#xff09;&#xff0c;求最小生成树&#xff08;minspantree&#xff09; 文章目录 求最短路径&#xff08;graphshortestpath&#xff09;&#xff0c;求最小生成树&#xff08;minspantree&#xff09;1、最短路径问题2、最小生成…...

用win系统搭建Minecraft世界服务器,MC开服教程,小白开服教程

雨云VPS用Windows系统搭建我的世界世界服务器&#xff0c;Minecraft开服教程&#xff0c;小白开服教程&#xff0c;MC 1.19.4版本服务器搭建教程。 此教程使用 Mohist 1.19.4 服务端&#xff0c;此服务端支持Forge模组和Bukkit/Spigot/Paper插件&#xff0c;如果需要开其他服务…...

MacOS安装Miniforge、Tensorflow、Jupyter Lab等(2024年最新)

大家好&#xff0c;我是邵奈一&#xff0c;一个不务正业的程序猿、正儿八经的斜杠青年。 1、世人称我为&#xff1a;被代码耽误的诗人、没天赋的书法家、五音不全的歌手、专业跑龙套演员、不合格的运动员… 2、这几年&#xff0c;我整理了很多IT技术相关的教程给大家&#xff0…...

iOS 应用上架指南:资料填写及提交审核

摘要 本文提供了iOS新站上架资料填写及提交审核的详细指南&#xff0c;包括创建应用、资料填写-综合、资料填写-IOS App和提交审核等步骤。通过本指南&#xff0c;您将了解到如何填写正确的资料&#xff0c;并顺利通过苹果公司的审核。 引言 在开发iOS应用后&#xff0c;将其…...

车速预测 | Matlab基于RBF径向基神经网络的车速预测模型(多步预测,尾巴图)

目录 效果一览基本介绍程序设计参考资料 效果一览 基本介绍 车速预测 | Matlab基于RBF径向基神经网络的车速预测模型&#xff08;多步预测&#xff0c;尾巴图&#xff09; 程序设计 完整程序和数据获取方式&#xff1a;私信博主回复Matlab基于RBF径向基神经网络的车速预测模型…...

MySQL 5.7.35下载安装使用_忘记密码_远程授权

文章目录 MySQL 5.7.35下载安装使用_忘记密码_远程授权MySQL下载地址mysql安装点击安装&#xff0c;最好以管理员身份运行选择自定义安装选择64位勾选启动自定义产品执行点击同意点击下一步点击执行下一步配置数据库端口号设置登录密码&#xff0c;如果密码忘记&#xff0c;下面…...

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 &#xff0c;你可以向其中任何位置插入 “a”、“b” 或 “c” 任意次&#xff0c;返回使 word 有效需要插入的最少字母数。 如果字符串可以由 “abc” 串联多次得到&#xff0c;则认为该字符串有效 。 示例 1&#xff1a; 输入&#xff1a;word “b” …...

ssm+vue的城投公司企业人事管理系统设计与实现(有报告)。Javaee项目,ssm vue前后端分离项目。

演示视频&#xff1a; ssmvue的城投公司企业人事管理系统设计与实现&#xff08;有报告&#xff09;。Javaee项目&#xff0c;ssm vue前后端分离项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#x…...

nginx基础面试题以及配置文件解析和命令控制

目录 1、nginx是什么 2、nginx的特点 3、为什么中国大陆有&#xff1a;百度、京东、新浪、网易、腾讯、淘宝等这么多用户使用nginx 4、nginx 的内部技术架构 上一期我们配置安装了nginx接着讲一下nginx配置文件的解析和nginx 命令控制 感谢观看&#xff01;希望能够帮助到…...

全自动网页生成系统网站源码重构版

源码优点: 所有模板经过精心审核与修改&#xff0c;完美兼容小屏手机大屏手机&#xff0c;以及各种平板端、电脑端和360浏览器、谷歌浏览器、火狐浏览器等等各大浏览器显示。 免费制作 为用户使用方便考虑&#xff0c;全自动网页制作系统无需繁琐的注册与登入&#xff0c;直…...

【算法每日一练]-动态规划 (保姆级教程 篇16) #纸带 #围栏木桩 #四柱河内塔

目录 今日知识点&#xff1a; 计算最长子序列的方案个数&#xff0c;类似最短路径个数问题 四柱河内塔问题&#xff1a;dp[i]min{ (p[i-k]f[k])dp[i-k] } 纸带 围栏木桩 四柱河内塔 纸带 思路&#xff1a; 我们先设置dp[i]表示从i到n的方案数。 那么减法操作中&#xff…...

Grounding 模型 + SAM 报错

引入 Grounding 目标检测模型串联 SAM 从而实现实例分割任务&#xff0c;目前支持 Grounding DINO 和 GLIP 参考教程 MMDetection-SAM 如果是 Grounding DINO 则安装如下依赖即可 cd playground pip install githttps://github.com/facebookresearch/segment-anything.git pip…...

linux 网络基础配置

将Linux主机接入到网络&#xff0c;需要配置网络相关设置一般包括如下内容&#xff1a; 主机名 iP/netmask (ip地址&#xff0c;网关) 路由&#xff1a;默认网关 网络连接状态 DNS服务器 &#xff08;主DNS服务器 次DNS服务器 第三个DNS服务器&#xff09; 一、…...

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 &#xff0c;就可以认为这是一组 好数对 。 返回好数对的数目。 示例 1&#xff1a; 输入&#xff1a;nums [1,2,3,1,1,3] 输出&#xff1a;4 解释&#xff1a;有 4 组好数对&am…...

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

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. 查看链接器参数(如果没有勾选上面…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...

【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分

一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计&#xff0c;提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合&#xff1a;各模块职责清晰&#xff0c;便于独立开发…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。

1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj&#xff0c;再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...