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

[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.算法原理详解 思路&#xff1a; 确定状态表示 -> dp[i][j]的含义 走到dp[…...

ChatGPT移动应用收入在GPT-4o发布后迎来最大涨幅

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…...

汉语拼音 如何 转化成粤语拼音 的

将汉语拼音&#xff08;普通话拼音&#xff09;转化为粤语拼音涉及到对声母、韵母以及声调的对照和调整。以下是详细的转换步骤和注意事项&#xff1a; 一、转换步骤 识别普通话拼音的声母和韵母查找对应的粤语拼音声母和韵母应用粤语声调 二、声母对照表 普通话拼音粤语拼…...

本地电子邮件测试工具-MailHog

通过MailHog&#xff0c;可以在浏览器中查看本机发的邮件内容&#xff0c;而无需发送到外网。 https://github.com/mailhog/MailHog在 macOS 环境下&#xff0c;下载文件后: 添加可执行权限:chmod x MailHog_darwin_amd64 运行:./MailHog_darwin_amd64 浏览器打开查看邮件:htt…...

Java18新特性

Java 18引入了若干新特性&#xff0c;以增强语言的功能性和性能。具体如下&#xff1a; 服务提供者接口&#xff08;Service Provider Interfaces, SPI&#xff09;&#xff1a;允许开发者为Java模块系统定义服务加载机制&#xff0c;从而能够更灵活地发现和加载服务实现。简单…...

大象资讯:PostgreSQL 17 Beta 1 发布!

↑ 关注“少安事务所”公众号&#xff0c;欢迎⭐收藏&#xff0c;不错过精彩内容~ PostgreSQL 全球开发小组 发布于 2024-05-23 PostgreSQL 全球开发小组宣布&#xff0c;PostgreSQL 17 的第一个测试版本现已可供下载。此版本包含 PostgreSQL 17 正式发布时将提供的所有功能的预…...

Rust:如何在 Windows 的 Linux 子系统(WSL)下安装

一、安装步骤 在Windows Subsystem for Linux (WSL)下安装Rust&#xff0c;可以按照以下步骤进行&#xff1a; 打开WSL终端&#xff1a; 首先&#xff0c;确保你的WSL已经安装并正常运行。你可以在Windows搜索栏中输入“WSL”并选择你安装的Linux发行版&#xff08;如Ubuntu&a…...

工具分享:VsCode注释神器,koro1FileHeader

他是有官方Wiki的。 https://github.com/OBKoro1/koro1FileHeader/wiki/ 项目在GitHub上开源。以下摘录部分wiki&#xff0c;用作介绍分享在这里插入代码片 如何找到setting.json设置模板 简单的输入命令 打开VSCode命令面板: mac: command p window: ctrl p输入> Ope…...

水面漂浮物生活垃圾识别检测系统

水面漂浮物生活垃圾识别检测系统通过现场监控摄像机对河道湖面等水体进行实时监测&#xff0c;水面漂浮物生活垃圾识别检测系统借助智能视频分析技术和YOLO深度学习技术&#xff0c;系统能够自动识别和抓拍水面上的垃圾漂浮物。一旦系统检测到有垃圾漂浮在水面上&#xff0c;立…...

通过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性能信息&#xff0c;补充了INNODB性能模式表的特定重点领域。通过简单的查询&#xff0c;您可以检查系统的整体运行状况。通过更详细的查询&#xff0c;您可以诊断诸如性能瓶颈、资源短缺和应用程序问题等问题。 每个监视器表示InnoDB…...

React Native 之 定义全局状态管理库(九)

假设你正在使用基于单页面应用&#xff08;SPA&#xff09;的微前端框架。以下简化一个应用之间共享状态的例子。 1. 使用发布/订阅模式 // globalStateManager.js class GlobalStateManager { constructor() { this.subscribers {}; this.state {}; } subscribe(key…...

java线程池实战应用总结

一、线程池的创建方式 方式&#xff08;一&#xff09;&#xff1a;通过构造函数ThreadPoolExecutor()方式创建线程池 步骤1&#xff1a;先构建线程池 public class AsyncTaskExecutor {/*** 核心线程数*/private static final int corePoolSize 10;/*** 最大线程数*/priva…...

部署 harbor 创建私有项目

一在 Docker harbor 节点&#xff08;192.168.11.&#xff09;上操作 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插件自动采集并发布

主要功能&#xff1a; wordpress 插件主题系列支持自动采集并发布。 主要采集: 福缘&#xff0c;中创&#xff0c;冒泡 自动采集各大项目网进行整合发布到自己个人网站 插件话更新&#xff0c;减少网络请求&#xff0c;提升稳定性 代码完美开源 傻瓜式操作&#xff0c;一…...

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 =…...

在排序数组中查找元素的一个位置和最后一个位置-力扣

第一此次想到的解法是首先使用二分查找在排序数组中查找到一个指定元素&#xff0c;随后对该元素左右进行遍历&#xff0c;找到起始位置和结束位置&#xff0c;代码如下&#xff1a; class Solution { public:vector<int> searchRange(vector<int>& nums, int…...

系统分析师-案例分析-数据库

系统分析师-案例分析-数据库 更多软考资料 https://ruankao.blog.csdn.net/ 文章目录 系统分析师-案例分析-数据库数据库考察知识点规范化函数依赖范式1NF2NF3NF 规范化问题不规范化反规范化设计反规范化设计同步问题 并发控制性能优化完整性约束视图安全分布式数据库特点优点…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

SpringTask-03.入门案例

一.入门案例 启动类&#xff1a; package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...

LRU 缓存机制详解与实现(Java版) + 力扣解决

&#x1f4cc; LRU 缓存机制详解与实现&#xff08;Java版&#xff09; 一、&#x1f4d6; 问题背景 在日常开发中&#xff0c;我们经常会使用 缓存&#xff08;Cache&#xff09; 来提升性能。但由于内存有限&#xff0c;缓存不可能无限增长&#xff0c;于是需要策略决定&am…...

Python Einops库:深度学习中的张量操作革命

Einops&#xff08;爱因斯坦操作库&#xff09;就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库&#xff0c;用类似自然语言的表达式替代了晦涩的API调用&#xff0c;彻底改变了深度学习工程…...

逻辑回归暴力训练预测金融欺诈

简述 「使用逻辑回归暴力预测金融欺诈&#xff0c;并不断增加特征维度持续测试」的做法&#xff0c;体现了一种逐步建模与迭代验证的实验思路&#xff0c;在金融欺诈检测中非常有价值&#xff0c;本文作为一篇回顾性记录了早年间公司给某行做反欺诈预测用到的技术和思路。百度…...

PHP 8.5 即将发布:管道操作符、强力调试

前不久&#xff0c;PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5&#xff01;作为 PHP 语言的又一次重要迭代&#xff0c;PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是&#xff0c;借助强大的本地开发环境 ServBay&am…...