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

LeetCode 2304. 网格中的最小路径代价:DP

【LetMeFly】2304.网格中的最小路径代价:DP

力扣题目链接:https://leetcode.cn/problems/minimum-path-cost-in-a-grid/

给你一个下标从 0 开始的整数矩阵 grid ,矩阵大小为 m x n ,由从 0m * n - 1 的不同整数组成。你可以在此矩阵中,从一个单元格移动到 下一行 的任何其他单元格。如果你位于单元格 (x, y) ,且满足 x < m - 1 ,你可以移动到 (x + 1, 0), (x + 1, 1), ..., (x + 1, n - 1) 中的任何一个单元格。注意: 在最后一行中的单元格不能触发移动。

每次可能的移动都需要付出对应的代价,代价用一个下标从 0 开始的二维数组 moveCost 表示,该数组大小为 (m * n) x n ,其中 moveCost[i][j] 是从值为 i 的单元格移动到下一行第 j 列单元格的代价。从 grid 最后一行的单元格移动的代价可以忽略。

grid 一条路径的代价是:所有路径经过的单元格的 值之和 加上 所有移动的 代价之和 。从 第一行 任意单元格出发,返回到达 最后一行 任意单元格的最小路径代价

 

示例 1:

输入:grid = [[5,3],[4,0],[2,1]], moveCost = [[9,8],[1,5],[10,12],[18,6],[2,4],[14,3]]
输出:17
解释:最小代价的路径是 5 -> 0 -> 1 。
- 路径途经单元格值之和 5 + 0 + 1 = 6 。
- 从 5 移动到 0 的代价为 3 。
- 从 0 移动到 1 的代价为 8 。
路径总代价为 6 + 3 + 8 = 17 。

示例 2:

输入:grid = [[5,1,2],[4,0,3]], moveCost = [[12,10,15],[20,23,8],[21,7,1],[8,1,13],[9,10,25],[5,3,2]]
输出:6
解释:
最小代价的路径是 2 -> 3 。 
- 路径途经单元格值之和 2 + 3 = 5 。 
- 从 2 移动到 3 的代价为 1 。 
路径总代价为 5 + 1 = 6 。

 

提示:

  • m == grid.length
  • n == grid[i].length
  • 2 <= m, n <= 50
  • grid 由从 0m * n - 1 的不同整数组成
  • moveCost.length == m * n
  • moveCost[i].length == n
  • 1 <= moveCost[i][j] <= 100

方法一:DP

从倒数第二行开始往第一行遍历:

  • 对于这一行的每一个元素:
    • 计算出 从下一行的所有元素中来到这一行,增加值最小的那个
  • 这个元素加上下一行来的最小增加量

最终返回第一行中的最小元素即为答案。

  • 时间复杂度 O ( n m 2 ) O(nm^2) O(nm2),其中 s i z e ( g r i d ) = n × m size(grid)=n\times m size(grid)=n×m n n n m m m列)
  • 空间复杂度 O ( 1 ) O(1) O(1)

AC代码

C++
class Solution {
public:int minPathCost(vector<vector<int>>& grid, vector<vector<int>>& moveCost) {int n = grid.size(), m = grid[0].size();for (int i = n - 2; i >= 0; i--) {for (int j = 0; j < m; j++) {int m_ = 100000000;for (int k = 0; k < m; k++) {m_ = min(m_, grid[i + 1][k] + moveCost[grid[i][j]][k]);}grid[i][j] += m_;}}return *min_element(grid[0].begin(), grid[0].end());}
};
Python
# from typing import Listclass Solution:def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:n, m = len(grid), len(grid[0])for i in range(n - 2, -1, -1):for j in range(m):m_ = 100000000for k in range(m):m_ = min(m_, grid[i + 1][k] + moveCost[grid[i][j]][k])grid[i][j] += m_return min(grid[0])

同步发文于CSDN,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/134563145

相关文章:

LeetCode 2304. 网格中的最小路径代价:DP

【LetMeFly】2304.网格中的最小路径代价&#xff1a;DP 力扣题目链接&#xff1a;https://leetcode.cn/problems/minimum-path-cost-in-a-grid/ 给你一个下标从 0 开始的整数矩阵 grid &#xff0c;矩阵大小为 m x n &#xff0c;由从 0 到 m * n - 1 的不同整数组成。你可以…...

c 实用化的文本终端实时显示摄像头视频

因为采用yuv格式&#xff0c;帧率都很低。图像会拖影。把图像尺寸尽量缩小&#xff0c;能大大改善。现在最麻烦的是图像上有黑色的闪影&#xff0c;不知是为啥&#xff1f;如是framebuffer引起的就无解了。终于找到问题了&#xff0c;是在显示前加了一条用黑色清屏造成的&#…...

CSS中常用的伪类选择器

一 、伪类&#xff08;不存在的类&#xff0c;特殊的类&#xff09; -伪类用来描述一个元素的特殊状态 比如&#xff1a;第一个元素&#xff0c;被点击的元素&#xff0c;鼠标移入的元素 -特点&#xff1a;一般请情况下&#xff0c;使用&#xff1a;开头 1、 :first-child …...

【python学习】中级篇-数据库操作:SQLite

SQLite是一个轻量级的数据库引擎&#xff0c;它可以嵌入到各种应用程序中。以下是SQLite的基本用法&#xff1a; 创建数据库文件 import sqlite3# 连接到一个不存在的数据库文件&#xff0c;如果文件不存在&#xff0c;将会自动创建一个新的数据库文件 conn sqlite3.connect…...

汇编-PROTO声明过程

64位汇编 64 模式中&#xff0c;PROTO 伪指令指定程序的外部过程&#xff0c;示例如下&#xff1a; ExitProcess PROTO ;指定外部过程&#xff0c;不需要参数.code main PROCmov ebx, 0FFFFFFFFh mov ecx,0 ;结束程序call ExitProcess ;调用外部过程main ENDP END 32位…...

MYSQL事务操作

...

自动化测试——自动卸载软件

&#x1f4e2;专注于分享软件测试干货内容&#xff0c;欢迎点赞 &#x1f44d; 收藏 ⭐留言 &#x1f4dd; 如有错误敬请指正&#xff01;&#x1f4e2;交流讨论&#xff1a;欢迎加入我们一起学习&#xff01;&#x1f4e2;资源分享&#xff1a;耗时200小时精选的「软件测试」资…...

Linux - 系统调用(syscall)

说明 基于riscv64 soc linux_5.10.4平台&#xff0c;通过新增一个系统调用深入了解下系统调用实现原理。 简介 Linux 软件运行环境分为用户空间和内核空间&#xff0c;默认情况下&#xff0c;用户进程无法访问内核&#xff0c;既不能访问内核所在的内存空间&#xff0c;也不…...

c语言-冒泡排序

冒泡排序原理&#xff1a; 冒泡排序是一种简单直观的排序算法&#xff0c;它重复地遍历待排序的元素序列&#xff0c;比较相邻的两个元素&#xff0c;如果它们的顺序不符合要求&#xff08;例如升序要求前面的元素小于后面的元素&#xff09;&#xff0c;则交换它们的位置。遍历…...

Mysql面经

Select语句的执行顺序 1、from 子句组装来自不同数据源的数据&#xff1b; 2、where 子句基于指定的条件对记录行进行筛选&#xff1b; 3、group by 子句将数据划分为多个分组&#xff1b; 4、使用聚集函数进行计算&#xff1b;AVG() SUM() MAX() MIN() COUNT() 5、使用 havin…...

1panel可视化Docker面板安装与使用

官网地址1Panel - 现代化、开源的 Linux 服务器运维管理面板 文章目录 目录 文章目录 前言 一、环境准备 二、使用步骤 1.安装命令 2.一些命令 3.使用 总结 前言 一、环境准备 虚拟机centos 已经安装好docker和 Docker Compose 或者都没安装 1panel会帮你自动安装 二、使用…...

es6中的import导入模块 和 export导出模块

es6中的import导入模块 和 export导出模块 一、定义二、使用1.默认导出导入2..命名导出导入3.命名导出&#xff08;Named Export&#xff09;与默认导出&#xff08;Default Export&#xff09;结合使用 三、总结 一、定义 功能&#xff1a;用于导入和导出模块的内容。 静态加载…...

WordPress插件开发教程手册 — 钩子(Hooks)

钩子是用一段代码添加/修改另外一段代码的方式&#xff0c;是 WordPress插件和主题与 WordPress 内核交互的基础&#xff0c;钩子在 WordPress 内核中也被广泛使用。WordPress 中有两种钩子&#xff0c;Action 和 Filter。使用钩子时&#xff0c;我们需要先编写一个自定义函数作…...

Python开发运维:Celery连接Redis

目录 一、理论 1.Celery 二、实验 1.Windows11安装Redis 2.Python3.8环境中配置Celery 3.celery的多目录结构异步执行 4.celery简单结构下的定时任务 三、问题 1.Celery命令报错 2.执行Celery命令报错 3.Win11启动Celery报ValueErro错误 4.Pycharm 无法 import 同目…...

JSP:JDBC

JDBC&#xff08;Java Data Base Connectivity的缩写&#xff09;是Java程序操作数据库的API&#xff0c;也是Java程序与数据库相交互的一门技术。 JDBC是Java操作数据库的规范&#xff0c;由一组用Java语言编写的类和接口组成&#xff0c;它对数据库的操作提供基本方法&#…...

能否在一台电脑上安全地登录多个Facebook账号?

Facebook是一个流量大、用户多的平台&#xff0c;许多人可能需要在一台设备上管理多个Facebook账号&#xff0c;无论是出于个人或职业需求&#xff0c;都能带来极大地便利。然而&#xff0c;保持每个账号的安全性和隐私性却是一个挑战。本文将介绍如何在一台电脑上安全地登录多…...

Banana Pi [BPi-R3-Mini] 回顾和主线 ImmortalWrt 固件支持

BananaPi BPi-R3 Mini 采用 MediaTek 830&#xff08;4 个 A53&#xff0c;最高 2.0 GHz&#xff09;&#xff0c;具有 2 个 2.5 GbE、AX4200 2.4G/5G 无线和 USB 2.0 端口。它还具有两个 M.2 连接器&#xff0c;可用于 NVMe SSD 和 5G 模块&#xff08;板上包含 Nano SIM 插槽…...

2001-2022年上市公-供应链话语权测算数据(原始数据+处理代码Stata do文档+结果)

2001-2022年上市公-供应链话语权测算数据&#xff08;原始数据处理代码Stata do文档结果&#xff09; 1、时间&#xff1a;2001-2022年 2、指标&#xff1a;企业代码、股票代码、年份、股票简称、上市公司前五大供应商的采购额之和占企业当年总采购额的比例、上市公司前五大客…...

如何通过ShardingJDBC进行读写分离

背景信息&#xff1a; 面对日益增加的系统访问量&#xff0c;数据库的吞吐量面临着巨大瓶颈。 对于同一时刻有大量并发读操作和较少写操作类型的应用系统来说&#xff0c;将数据库拆分为主库和从库。其中主库负责处理事务性的增删改操作&#xff0c;从库负责处理查询操作&#…...

【uniapp】部分图标点击事件无反应

比如&#xff1a;点击这个图标在h5都正常&#xff0c;在小程序上无反应 css&#xff1a;也设置z-index&#xff0c;padding 页面上也试过click.native.stop.prevent"changePassword()" 时而可以时而不行&#xff0c; 最后发现是手机里输入键盘的原因&#xff0c;输…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

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

作为测试我们应该关注redis哪些方面

1、功能测试 数据结构操作&#xff1a;验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化&#xff1a;测试aof和aof持久化机制&#xff0c;确保数据在开启后正确恢复。 事务&#xff1a;检查事务的原子性和回滚机制。 发布订阅&#xff1a;确保消息正确传递。 2、性…...