[Algorithm][动态规划][路径问题][不同路径][不同路径Ⅱ][珠宝的最高价值]详细讲解
目录
- 1.不同路径
- 1.题目链接
- 2.算法原理详解
- 3.代码实现
- 2.不同路径 II
- 1.题目链接
- 2.算法原理详解
- 3.代码实现
- 3.珠宝的最高价值
- 1.题目链接
- 2.算法原理详解
- 3.代码实现
1.不同路径
1.题目链接
- 不同路径
2.算法原理详解
- 思路:
-
确定状态表示 ->
dp[i][j]的含义- 走到
dp[i][j]的时候,一共有多少种方式

- 走到
-
推导状态转移方程
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
-
初始化:
dp表多开一行和一列虚拟结点,避免处理边界dp[0][1] = 1 || dp[1][0] = 1

-
确定填表顺序:从上往下,从左往右
-
确定返回值:
dp[n][m]
-
- 上述如果
dp表不多开那一行和一列虚拟结点会怎么样?- 需要做边界处理,将第一列和第一行先初始化为1
3.代码实现
int uniquePaths(int n, int m)
{vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));dp[0][1] = 1;for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}return dp[n][m];
}
2.不同路径 II
1.题目链接
- 不同路径 II
2.算法原理详解
- 思路:
-
确定状态表示 ->
dp[i][j]的含义- 走到
dp[i][j]的时候,一共有多少种方式

- 走到
-
推导状态转移方程
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

-
初始化:
dp表多开一行和一列虚拟结点,避免处理边界dp[0][1] = 1 || dp[1][0] = 1

-
确定填表顺序:从上往下,从左往右
-
确定返回值:
dp[n][m]
-
3.代码实现
int uniquePathsWithObstacles(vector<vector<int>>& ob)
{int n = ob.size(), m = ob[0].size();vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));dp[0][1] = 1;for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){if(ob[i - 1][j - 1] == 0) // 注意下表映射关系{dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}}return dp[n][m];
}
3.珠宝的最高价值
1.题目链接
- 珠宝的最高价值
2.算法原理详解
- 思路:
-
确定状态表示 ->
dp[i][j]的含义- 到达
dp[i][j]的时候,此时的最大价值
- 到达
-
推导状态转移方程
dp[i][j] = max(dp[i - 1][j] + dp[i][j - 1]) + g[i][j]

-
初始化:
dp表多开一行和一列虚拟结点,避免处理边界- 第一行和第一列全部初始化为0即可
-
确定填表顺序:从上往下,从左往右
-
确定返回值:
dp[n][m]
-
3.代码实现
int jewelleryValue(vector<vector<int>>& frame)
{int n = frame.size(), m = frame[0].size();vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + frame[i - 1][j - 1];}}return dp[n][m];
}
相关文章:
[Algorithm][动态规划][路径问题][不同路径][不同路径Ⅱ][珠宝的最高价值]详细讲解
目录 1.不同路径1.题目链接2.算法原理详解3.代码实现 2.不同路径 II1.题目链接2.算法原理详解3.代码实现 3.珠宝的最高价值1.题目链接2.算法原理详解3.代码实现 1.不同路径 1.题目链接 不同路径 2.算法原理详解 思路: 确定状态表示 -> dp[i][j]的含义 走到dp[…...
ChatGPT移动应用收入在GPT-4o发布后迎来最大涨幅
每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗?订阅我们的简报,深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同,从行业内部的深度分析和实用指南中受益。不要错过这个机会,成为AI领…...
汉语拼音 如何 转化成粤语拼音 的
将汉语拼音(普通话拼音)转化为粤语拼音涉及到对声母、韵母以及声调的对照和调整。以下是详细的转换步骤和注意事项: 一、转换步骤 识别普通话拼音的声母和韵母查找对应的粤语拼音声母和韵母应用粤语声调 二、声母对照表 普通话拼音粤语拼…...
本地电子邮件测试工具-MailHog
通过MailHog,可以在浏览器中查看本机发的邮件内容,而无需发送到外网。 https://github.com/mailhog/MailHog在 macOS 环境下,下载文件后: 添加可执行权限:chmod x MailHog_darwin_amd64 运行:./MailHog_darwin_amd64 浏览器打开查看邮件:htt…...
Java18新特性
Java 18引入了若干新特性,以增强语言的功能性和性能。具体如下: 服务提供者接口(Service Provider Interfaces, SPI):允许开发者为Java模块系统定义服务加载机制,从而能够更灵活地发现和加载服务实现。简单…...
大象资讯:PostgreSQL 17 Beta 1 发布!
↑ 关注“少安事务所”公众号,欢迎⭐收藏,不错过精彩内容~ PostgreSQL 全球开发小组 发布于 2024-05-23 PostgreSQL 全球开发小组宣布,PostgreSQL 17 的第一个测试版本现已可供下载。此版本包含 PostgreSQL 17 正式发布时将提供的所有功能的预…...
Rust:如何在 Windows 的 Linux 子系统(WSL)下安装
一、安装步骤 在Windows Subsystem for Linux (WSL)下安装Rust,可以按照以下步骤进行: 打开WSL终端: 首先,确保你的WSL已经安装并正常运行。你可以在Windows搜索栏中输入“WSL”并选择你安装的Linux发行版(如Ubuntu&a…...
工具分享:VsCode注释神器,koro1FileHeader
他是有官方Wiki的。 https://github.com/OBKoro1/koro1FileHeader/wiki/ 项目在GitHub上开源。以下摘录部分wiki,用作介绍分享在这里插入代码片 如何找到setting.json设置模板 简单的输入命令 打开VSCode命令面板: mac: command p window: ctrl p输入> Ope…...
水面漂浮物生活垃圾识别检测系统
水面漂浮物生活垃圾识别检测系统通过现场监控摄像机对河道湖面等水体进行实时监测,水面漂浮物生活垃圾识别检测系统借助智能视频分析技术和YOLO深度学习技术,系统能够自动识别和抓拍水面上的垃圾漂浮物。一旦系统检测到有垃圾漂浮在水面上,立…...
通过python读取并发送二进制文件到串口
代码 #!python.exe """ filename send_bin.py brief According to the users input, read bin file, subpackage and send the file by UART. HowToUse send_bin.py -h author shadowThreeDgmail.com data 20220224 &q…...
前端笔记-day07
学成在线网站 文章目录 效果图代码展示index.htmlindex.cssbase.css 效果图 代码展示 index.html <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-w…...
【MySQL精通之路】INFORMATION_SCHEMA库-INNODB_METRICS表
INNODB_METRICS表提供了各种各样的INNODB性能信息,补充了INNODB性能模式表的特定重点领域。通过简单的查询,您可以检查系统的整体运行状况。通过更详细的查询,您可以诊断诸如性能瓶颈、资源短缺和应用程序问题等问题。 每个监视器表示InnoDB…...
React Native 之 定义全局状态管理库(九)
假设你正在使用基于单页面应用(SPA)的微前端框架。以下简化一个应用之间共享状态的例子。 1. 使用发布/订阅模式 // globalStateManager.js class GlobalStateManager { constructor() { this.subscribers {}; this.state {}; } subscribe(key…...
java线程池实战应用总结
一、线程池的创建方式 方式(一):通过构造函数ThreadPoolExecutor()方式创建线程池 步骤1:先构建线程池 public class AsyncTaskExecutor {/*** 核心线程数*/private static final int corePoolSize 10;/*** 最大线程数*/priva…...
部署 harbor 创建私有项目
一在 Docker harbor 节点(192.168.11.)上操作 1 关闭防火墙防护 systemctl stop firewalld.service systemctl disable firewalld.service setenforce 0 2 安装docker yum install -y yum-utils device-mapper-persistent-data lvm2 yum-config-ma…...
在Linux系统中解决Java生成海报文字乱码和缺少字体文件的问题
在Linux系统中,如果缺少特定的字体文件,可以通过以下几种方法来解决: 1. 安装系统字体包 大多数Linux发行版提供了各种字体包,可以通过包管理器安装这些字体包。例如,在Debian/Ubuntu系统上,可以使用以下命令安装常见的字体包: # 安装基本的字体包 sudo apt-get updat…...
升级版网创教程wordpress插件自动采集并发布
主要功能: wordpress 插件主题系列支持自动采集并发布。 主要采集: 福缘,中创,冒泡 自动采集各大项目网进行整合发布到自己个人网站 插件话更新,减少网络请求,提升稳定性 代码完美开源 傻瓜式操作,一…...
MySQL 视图(1)
常用视图语句 -- 创建视图 CREATE VIEW t1_view AS SELECT * FROM t1; CREATE VIEW v AS VALUES ROW(1,2);-- 查询视图 SELECT * FROM t1_view;-- 查询视图的相关系统视图 SELECT VIEW_DEFINITION FROM INFORMATION_SCHEMA.VIEWS WHERE TABLE_SCHEMA = test AND TABLE_NAME =…...
在排序数组中查找元素的一个位置和最后一个位置-力扣
第一此次想到的解法是首先使用二分查找在排序数组中查找到一个指定元素,随后对该元素左右进行遍历,找到起始位置和结束位置,代码如下: class Solution { public:vector<int> searchRange(vector<int>& nums, int…...
系统分析师-案例分析-数据库
系统分析师-案例分析-数据库 更多软考资料 https://ruankao.blog.csdn.net/ 文章目录 系统分析师-案例分析-数据库数据库考察知识点规范化函数依赖范式1NF2NF3NF 规范化问题不规范化反规范化设计反规范化设计同步问题 并发控制性能优化完整性约束视图安全分布式数据库特点优点…...
OpenClaw语音交互方案:Qwen3-32B镜像对接Whisper实时转写
OpenClaw语音交互方案:Qwen3-32B镜像对接Whisper实时转写 1. 为什么需要语音交互方案 作为一个长期与命令行打交道的开发者,我始终在寻找更自然的交互方式。键盘输入固然高效,但在某些场景下——比如双手被占用时调试代码、厨房里边做饭边查…...
FireRedASR-AED-L在软件测试中的应用:语音交互功能自动化测试
FireRedASR-AED-L在软件测试中的应用:语音交互功能自动化测试 你有没有想过,那些能听懂你说话的手机应用、智能音箱或者车载系统,它们的“听力”到底准不准?开发团队是怎么确保你每次说“播放音乐”或者“导航回家”,…...
从数据流视角看训练:你的GPU/TPU是如何‘吃’数据的?Epoch、Batch与迭代的硬件协同
从数据流视角看训练:你的GPU/TPU是如何‘吃’数据的?Epoch、Batch与迭代的硬件协同 当你在深夜盯着屏幕上缓慢跳动的训练进度条时,是否好奇过那些被吞进GPU的数据究竟经历了怎样的旅程?本文将带你从硬件执行层的独特视角ÿ…...
Spring Boot项目实战:5步搞定sa-token与OAuth2.0的无缝整合(附完整代码)
Spring Boot项目实战:5步搞定sa-token与OAuth2.0的无缝整合(附完整代码) 在当今微服务架构盛行的时代,认证授权已成为系统设计中不可或缺的一环。对于Java开发者而言,如何在保持代码简洁的同时实现强大的权限控制&…...
5分钟搭建专业级缠论可视化分析平台:从零到实战的完整指南
5分钟搭建专业级缠论可视化分析平台:从零到实战的完整指南 【免费下载链接】chanvis 基于TradingView本地SDK的可视化前后端代码,适用于缠论量化研究,和其他的基于几何交易的量化研究。 缠论量化 摩尔缠论 缠论可视化 TradingView TV-SDK 项…...
杭州做生成式引擎优化的服务公司有哪些?
杭州做生成式引擎优化的服务公司有哪些? 一、行业背景:GEO已成为AI时代企业增长的核心基建 生成式引擎优化(GEO,Generative Engine Optimization),是针对大语言模型的检索逻辑与回答规则,优化企…...
如何打造个人游戏云:5步掌握Sunshine跨平台串流技术
如何打造个人游戏云:5步掌握Sunshine跨平台串流技术 【免费下载链接】Sunshine Sunshine: Sunshine是一个自托管的游戏流媒体服务器,支持通过Moonlight在各种设备上进行低延迟的游戏串流。 项目地址: https://gitcode.com/GitHub_Trending/su/Sunshine…...
PX4飞控系统深度解析:从模块化架构到自主飞行核心技术揭秘
PX4飞控系统深度解析:从模块化架构到自主飞行核心技术揭秘 【免费下载链接】PX4-Autopilot PX4 Autopilot Software 项目地址: https://gitcode.com/gh_mirrors/px/PX4-Autopilot 你是否曾好奇,一个开源飞控系统如何支撑从微型无人机到工业级无人…...
别再手动重启了!CRMEB定时任务修改后,这两种生效方式你选对了吗?
CRMEB定时任务深度解析:两种触发模式的选择与实战优化 在电商系统运维中,定时任务如同隐形的齿轮,默默推动着优惠券发放、订单状态更新、数据报表生成等关键业务流程。CRMEB作为基于ThinkPHP6的成熟电商解决方案,其定时任务模块设…...
LingBot-Depth部署避坑指南:常见问题与解决方案汇总
LingBot-Depth部署避坑指南:常见问题与解决方案汇总 1. 引言:为什么需要这份指南 当你第一次尝试部署LingBot-Depth时,可能会遇到各种意想不到的问题——从模型下载失败到GPU内存不足,从端口冲突到奇怪的输出结果。这些问题往往…...
