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

LeetCode 热题 100_最小路径和（92_64_中等_C++）（多维动态规划）

news 来源：原创 2025/5/23 1:57:31

LeetCode 热题 100_最小路径和（92_64）

- 题目描述：
- 输入输出样例：
- 题解：
- - 解题思路：
  - - 思路一（多维动态规划）：
  - 代码实现
  - - 代码实现（思路一（多维动态规划））：
    - 以思路一为例进行调试

题目描述：

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

**说明：**每次只能向下或者向右移动一步。

输入输出样例：

示例 1：
在这里插入图片描述

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：
输入：grid = [[1,2,3],[4,5,6]]
输出：12

提示：
m== grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 200

题解：

解题思路：

思路一（多维动态规划）：

1、题目要求每次只能向下或者向右移动一步。则一个位置的元素可由左方和上方的位置移动而来。

dp[ i ][ j ]为路径上的数字总和最小。
dp[ i ][ j ] = min(dp[ i-1 ][ j ],dp[ i ][ j-1 ])+grid[ i ][ j ]。
dp[ 0 ][ 0 ] = grid[ 0 ][ 0 ]。
dp[ 0 ][ j ] = dp[ 0 ][ j-1 ]+grid[ 0 ][ j ]。第一行的元素只能由左侧元素移动得来。
dp[ i ][ 0 ] = dp[ i-1 ][ 0 ]+grid[ 0 ][ j ]。第一列的元素只能由上侧元素移动得来。

2、复杂度分析：
① 时间复杂度：O(mn)，其中 m 和 n 分别是网格的行数和列数。需要对整个网格遍历一次，计算 dp 的每个元素的值。
② 空间复杂度：O(mn)，其中 m 和 n 分别是网格的行数和列数。创建一个二维数组 dp，和网格大小相同(也可使用一维dp数组：参考LeetCode 热题 100_不同路径（91_62_中等_C++）)。

代码实现

代码实现（思路一（多维动态规划））：

class Solution {
public:// 计算从左上角到右下角的最小路径和int minPathSum(vector<vector<int>>& grid) {// 创建一个dp数组，用于存储从起点到达每个格子的最小路径和vector<vector<int>> dp(grid.size(), vector<int>(grid[0].size()));// 初始化dp数组的起始位置，起点的路径和就是grid[0][0]的值dp[0][0] = grid[0][0];// 处理第一行，从左到右累加// 因为只能从左边的格子走到当前格子，所以每一行的第一个格子的路径和是累加的for (int j = 1; j < grid[0].size(); j++) {dp[0][j] = dp[0][j - 1] + grid[0][j];}// 处理第一列，从上到下累加// 因为只能从上方的格子走到当前格子，所以每一列的第一个格子的路径和是累加的for (int i = 1; i < grid.size(); i++) {dp[i][0] = dp[i - 1][0] + grid[i][0];}// 从(1, 1)开始，遍历整个grid// 每个格子的最小路径和是从它的上方格子或者左方格子中选择较小的路径和，再加上当前格子的值for (int i = 1; i < grid.size(); i++) {for (int j = 1; j < grid[0].size(); j++) {dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];}}// 返回右下角的最小路径和，即dp数组的右下角元素return dp[grid.size() - 1][grid[0].size() - 1];}
};

以思路一为例进行调试

#include<iostream>
#include<vector>
using namespace std;class Solution {
public:// 计算从左上角到右下角的最小路径和int minPathSum(vector<vector<int>>& grid) {// 创建一个dp数组，用于存储从起点到达每个格子的最小路径和vector<vector<int>> dp(grid.size(), vector<int>(grid[0].size()));// 初始化dp数组的起始位置，起点的路径和就是grid[0][0]的值dp[0][0] = grid[0][0];// 处理第一行，从左到右累加// 因为只能从左边的格子走到当前格子，所以每一行的第一个格子的路径和是累加的for (int j = 1; j < grid[0].size(); j++) {dp[0][j] = dp[0][j - 1] + grid[0][j];}// 处理第一列，从上到下累加// 因为只能从上方的格子走到当前格子，所以每一列的第一个格子的路径和是累加的for (int i = 1; i < grid.size(); i++) {dp[i][0] = dp[i - 1][0] + grid[i][0];}// 从(1, 1)开始，遍历整个grid// 每个格子的最小路径和是从它的上方格子或者左方格子中选择较小的路径和，再加上当前格子的值for (int i = 1; i < grid.size(); i++) {for (int j = 1; j < grid[0].size(); j++) {dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];}}// 返回右下角的最小路径和，即dp数组的右下角元素return dp[grid.size() - 1][grid[0].size() - 1];}
};int main(int argc, char const *argv[])
{vector<vector<int>> grid={{1,3,1},{1,5,1},{4,2,1}};Solution s;cout<<s.minPathSum(grid);return 0;
}

LeetCode 热题 100_最小路径和（92_64)原题链接
欢迎大家和我沟通交流(✿◠‿◠)

LeetCode 热题 100_最小路径和（92_64_中等_C++）（多维动态规划）

LeetCode 热题 100_最小路径和（92_64） 题目描述：输入输出样例：题解：解题思路：思路一（多维动态规划）： 代码实现代码实现（思路一（多维动态规划&…...

编程日记 2025/5/23 1:57:31

关于常量指针和指向常量的指针

关于指针，对于常量指针和指向常量的指针也是傻傻分不清。看到定义时，不知道是指针不能变，还是指针指向的内容不能变量。先看形式： const char * A; char * const B; 这两种有什么区别？傻傻分不清。 A这种定义&am…...

编程日记 2025/5/22 22:50:06

新时代下的存储过程开发实践与优化

随着现代应用系统的复杂度不断增加，数据库作为核心的数据存储和处理引擎，其性能和可靠性显得尤为重要。存储过程（Stored Procedure）作为一种封装在数据库中的应用逻辑，使得开发者能够在数据库层面实现数据操作、数据校…...

编程日记 2025/5/22 5:53:41

4月28日日记

2025年4月28日星期一晴今天过得格外充实，也充满了收获与喜悦。下午，我参加了学校的五四述职大会。各个学院的团委书记依次上台，汇报过去一年的工作成果。看着大家在台上分享着各自学院的精彩故事，我深受触动。他们所展示的活…...

编程日记 2025/5/20 4:11:34

大模型性能测试

当我们部署了大模型并对外提供服务时，我们通常都想了解一下大模型能够支持多少个并发访问，在不同的并发数下，模型的性能如何。了解这些信息有助于我们更好的对算力进行评估，为用户带来更好的性能体验。大模型通常是通过API接口的…...

编程日记 2025/5/3 8:04:05

利用 Google Earth Engine 探索江宁区 2010 - 2020 年 EVI 时空变化

引言增强型植被指数（Enhanced Vegetation Index，EVI）是一种用于量化植被生长状态和覆盖程度的重要指标，它在监测植被动态、生态环境评估以及气候变化研究等领域发挥着关键作用。Google Earth Engine（GEE）…...

编程日记 2025/5/20 13:52:29

IEC 61850标准协议解读 2.基于Java的MMS实现

专栏文章目录第一章 IEC 61850标准协议解读 0.导言第二章 IEC 61850标准协议解读 1.建模讲解第三章 IEC 61850标准协议解读 2.基于Java的MMS实现目录专栏文章目录前言1 依赖库引入2 创建服务端3 创建客户端4 读写模型4.1 服务端读写4.2 客户端读写 5.报告6 文件服务6.1 读…...

编程日记 2025/5/23 1:48:34

花费7元训练自己的GPT 2模型

在上一篇博客中，我介绍了用Tensorflow来重现GPT 1的模型和训练的过程。这次我打算用Pytorch来重现GPT 2的模型并从头进行训练。 GPT 2的模型相比GPT 1的改进并不多，主要在以下方面： 1. GPT 2把layer normalization放在每个decoder block的前…...

编程日记 2025/5/21 10:07:00

【android bluetooth 协议分析 06】【l2cap详解 10】【通过avdtp连接流程,感受l2cap通道的生命周期变化】

本篇我们通过分析一个具体的实例，来直观感受一下 l2cap 中通道的状态变化。 1. 环境描述： 车机： a2dp sink手机: a2dp source场景： 手机主动触发连车机声明一下： 分析的btsnoop 和 logcat 还有源码，…...

编程日记 2025/5/23 1:28:44

如何在idea中写spark程序。

要在IntelliJ IDEA中编写Spark程序，你可以按照以下步骤进行： 1. 安装和配置Java：确保你的计算机上已经安装了Java Development Kit (JDK)，并且已配置好 JAVA_HOME 环境变量。 2. 安装IntelliJ IDEA：下载并安装Inte…...

编程日记 2025/5/22 20:43:53

Pytest-mark使用详解（跳过、标记、参数化)

1.前言在工作中我们经常使用pytest.mark.XXXX进行装饰器修饰，后面的XXX的不同，在pytest中有不同的作用，其整体使用相对复杂，我们单独将其抽取出来做详细的讲解。 2.pytest.mark.skip()/skipif()跳过用例 import pytest #无条…...

编程日记 2025/5/23 1:13:22

[Android] GKD v1.10.3

[Android] GKD 链接：https://pan.xunlei.com/s/VOOwKvmwpLoLl7fLi6wJZKK-A1?pwd8mey# GKD（详情请戳作者项目地址）是一款免费开源简洁多规则的自动跳过广告的软件，整体基于kotlin开发，免root即可使用。简而言之&am…...

编程日记 2025/5/23 1:32:27

C22-作业练习之最大公约数与最小公倍数

作业练习之最大公约数与最小公倍数代码 #include <stdio.h> int main() {//变量初始化int m,n;int i,gcd,lcm;//数据录入printf("请输入两个整数:");scanf("%d %d",&m,&n);//求最大公约数int min(m<n)?m:n; //找m与n的最小值for(imi…...

编程日记 2025/5/23 1:11:59

信号完整性简介第一篇

本章将讲述信号完整性相关问题。首先提出什么是高速系统设计中的信号完整性，其次结合影响信号完整性的各种因素，深入讨论在高速系统设计过程中会碰到的几类信号完整性问题，并对每一类问题提出相应的预防措施和解决方案。需要说明&#xff0…...

编程日记 2025/5/1 3:07:00

Qt开发环境的安装与问题的解决（2）

文章目录 1. Qt开发环境安装的说明2. 通过安装包进行安装3. 通过在线下载程序解决问题下载 https....网路错误问题解决开始安装--第一部分开始安装--第二部分 4. 建议配置环境变量（非必须）配置环境变量的意义简介：这篇文章主要分享Qt开发环…...

编程日记 2025/5/18 22:34:14

STM32 ADC模数转换器

一、ADC简介 ADC（Analog-Digital Converter）模拟-数字转换器ADC可以将引脚上连续变化的模拟电压转换为内存中存储的数字变量，建立模拟电路到数字电路的桥梁12位逐次逼近型ADC，1us转换时间输入电压范围：0~3.3V&#x…...

编程日记 2025/5/20 12:06:29

World of Warcraft [CLASSIC] Hunter[Grandel] R12

World of Warcraft [CLASSIC] Hunter[Grandel] R12 R13，[Freeblue] 可惜当时没有截图，唉，没有纪念 --- 挂机脚本...

编程日记 2025/5/23 1:55:50

kalibr：相机模型

文章目录 📚简介Kalibr标定支持的相机模型及适用场景📌 针孔相机模型（Pinhole）🌐 全向相机模型（Omnidirectional）🔍 特殊模型💡 选型建议⚠️ 注意事项📚简介 Kalibr作为多传感器标定的重要工具，支持多种相机模型以适应不同光学特性的视觉传感器。其核心相机…...

编程日记 2025/5/11 7:29:24

【AI News | 20250428】每日AI进展

AI Repos 1、dyad Dyad 是一款免费开源的本地化 AI 应用开发工具，兼容 Windows 和 Mac 双平台。支持使用自有 API 密钥灵活调用主流 AI 模型（包括 Gemini、GPT-4.1、Claude 等），内置数据库与身份验证系统可快速构建完整应用。 …...

编程日记 2025/5/23 1:00:57

DNS区域的类型

在BIND9中，type 用于定义DNS区域的类型，不同的类型决定了BIND如何处理该区域的DNS数据。以下是主要的类型及其作用详解： 1. master（主区域） 作用： 表示该区域是权威DNS服务器的主副本，负责存储…...

编程日记 2025/5/18 0:24:31

HTTP vs HTTPS：传输协议的安全演进与核心差异

HTTP（HyperText Transfer Protocol）和HTTPS（HTTP Secure）作为两种最常用的协议，其安全性和实现方式直接关系到用户隐私和数据完整性。目录一、HTTP与HTTPS的基础概念二、HTTP与HTTPS的核心差异 …...

编程日记 2025/5/23 1:53:49

Android平台Unity引擎的Mono JIT机制分析

一、分析背景 Unity引擎开发游戏采用了C#语言，Unity采用了Mono的Jit机制实现C#逻辑代码动态编译和执行，Mono属于开源的工程，可通过查看Mono源码了解其中的处理。本文针对Mono的Jit动态编译和执行的机制进行分析，更好的了解Unity引擎在Android平台所采用的处理方式。二、M…...

编程日记 2025/5/23 1:25:29

【java】接口

一、定义 1.接口中所有方法都是抽象方法和公共方法（可以省略 abstract、public），不可以有正常的方法，所有变量都是全局静态常量 2.能继承接口的只能是接口 3.接口和类的关系通过实现（重写（实现）…...

编程日记 2025/5/3 6:16:47

Vuex(二) —— 用Vuex完成购物车案例

目录需求需求分析组件分析组件通信开发准备环境准备模块结构商品列表组件展示商品列表添加购物车我的购物车组件购物车列表商品数量和统计功能删除购物车商品购物车列表组件购物车列表全选操作数字加减并统计小计删除功能统计总数量和总钱数处理金额小数的问题本地存…...

编程日记 2025/5/21 22:30:23

数字孪生的浪潮：从虚拟镜像到现实世界的 IT 变革

文章目录数字孪生的本质：物理与虚拟的实时镜像数字孪生的演进：从工业试验到全行业热潮核心技术：数字孪生的基石与工具链物联网（IoT）：数据采集云计算与大数据：模型存储AI 与机器学习&#xff1a…...

编程日记 2025/5/3 8:01:26

Web开发之三层架构

实例： 分层解耦耦合:衡量软件中各个层/各个模块的依赖关联程度。内聚:软件中各个功能模块内部的功能联系。软件设计原则:高内聚低耦合控制反转:Inversion 0f Control，简称IQC。对象的创建控制权由程序自身转移到外部(容器)，这种思想称为…...

编程日记 2025/5/15 22:42:51

社交电商和泛娱乐平台出海南美市场支付方式与策略

随着中国社交电商和泛娱乐平台加速全球化布局，南美市场凭借庞大的人口基数、快速增长的互联网渗透率和活跃的社交媒体使用率，成为出海企业的重要战略要地。然而，这片"新蓝海"的支付生态复杂多元，信用卡欺诈率高企，现金支付仍占主导，不同国家支付偏好差异显著。…...

编程日记 2025/5/23 1:08:13

Miniconda Windows10版本下载和安装

Miniconda Windows10版本下载和安装步骤1：Miniconda3下载和安装 # 1、下载地址（Windows 64位） https://repo.anaconda.com/miniconda/Miniconda3-latest-Windows-x86_64.exe #2、双击进行安装 # 安装注意事项： 1. 安装路径建议&a…...

编程日记 2025/5/23 1:45:22

编译原理：由浅入深从语法树到文法类型

文法与语言基础：从语法树到文法类型文法（Grammar）和语言（Language）是计算机科学和语言学中解析和理解语言结构的核心概念。无论是编程语言的编译器设计，还是自然语言处理（NLP）中的…...

编程日记 2025/5/23 1:13:23

初识Python

哈哈哈，为了让初学者对python进一步了解，懒惰的博主特地去问了AI，如何更加形象的形容python这一么语言 🌟 Python 是什么？ 想象一下，编程语言是一群性格各异的人： C语言：穿格子衫的…...

编程日记 2025/5/23 1:28:43

C++ —— 正向迭代器与反向迭代器

目录 1. 正向迭代器（Forward Iterator） 1.1 基本概念 1.2 核心特性 1.3 典型使用 1.4 重要特点 2. 反向迭代器（Reverse Iterator） 2.1 基本概念 2.2 核心特性 2.3 典型使用 2.4 重要特点 3. 正反迭代器对比 4. 正反迭代…...

编程日记 2025/5/22 1:55:20

FDA会议类型总结

1. 会议类型及目的 1.1 Type A会议 1.1.1 争议解决会议用于解决药物研发过程中与FDA产生的争议，明确双方分歧点。通过讨论达成共识，避免因争议影响研发进度。 1.1.2 临床保留讨论会议针对临床试验中出现的问题进行讨论，决定是否保留临床试验。综合评估临床试验的安全性…...

编程日记 2025/5/20 11:03:23

数据结构算法竞赛训练网站OJ（Online Judge)

都是个人使用过的算法训练OJ，存个档洛谷 https://www.luogu.org/ 个人使用最多的，题目较全，每题都有题解博客，社区比较完善。 PTA https://pintia.cn/ 学习数据结构和练习天梯赛的时候使用的。牛客 https://ac.nowcoder.co…...

编程日记 2025/4/29 15:42:09

快速搭建对象存储服务 - Minio，并解决临时地址暴露ip、短链接请求改变浏览器地址等问题

本文要解决的问题基础的Minio下载安装、java操作方法、完整的工具类。使用minio时需要注意的地方： 使用Minio的时候，生成资源的临时访问链接时，生成的地址IP是真实的IP和端口，不安全，怎么办？ 生成的Min…...

编程日记 2025/5/23 1:09:57

2025年- H11-Lc118-53.最大子数组和（普通数组）---java版

1.题目描述 2.思路用动态规划方法来解决【最大子数组和】（Maximum Subarray）问题。 pre（当前位置最大和）、 maxAns（全局最大和） 3.代码实现 class H53 {public int maxSubArray(int[] nums) {int curr…...

编程日记 2025/5/23 1:22:04

基于蓝牙Beacon人员导航方案

基于蓝牙Beacon人员导航方案一、室内定位市场痛点与技术选择大型商场（单层超2万㎡）和医院（科室超200个）的复杂空间中，传统GPS信号衰减超90%，用户平均寻路耗时10-15分钟，30%购物决策因“找店…...

编程日记 2025/4/29 15:38:51

mysql模糊多次OR查询某一个字段，针对这个字段进行查询分组

一. 需求有一个mysql表t_test,有两个字段className和studentStr 其中studentStr会用来模糊查询假如现在有6条数据 1.studentStr字段数据:“小明,小红,小同,小芳,小特,小兰” 2.studentStr字段数据:“小明,小红,小同” 3.studentStr字段数据:“小芳,小特,小兰” 4.stud…...

编程日记 2025/5/13 2:56:14

OpenGL进阶系列21 - OpenGL SuperBible - blendmatrix 例子学习

一：概述颜色输出阶段是 OpenGL 渲染管线中最后一个阶段。它决定了片段在离开片段着色器之后，最终显示在用户屏幕上的颜色值。颜色输出阶段最重要的一个操作就是混合。本例子重点介绍下OpenGL中的混合操作。对于每个通过片段测试（per-fragment tests）的片段，会执行混合操…...

编程日记 2025/4/29 15:38:46

阿里语音处理工具ClearerVoice-Studio项目上手指南

ClearerVoice-Studio：开源语音处理全能工具箱 🚀 核心功能速览语音增强：消除环境噪声（支持16kHz/48kHz）语音分离：多人对话场景的说话人分离（8kHz/16kHz）超分辨率：16kHz→48kHz音质提升目标说话人提取：基于人脸/手势/EEG的多模态提取语音质量评估：9种客观评价指标A…...

编程日记 2025/4/29 15:36:34

31、简要描述Promise.all的用途

Promise.all 是 JavaScript 中用于处理多个异步操作的核心方法，其核心用途是并行聚合多个 Promise 的结果，并在所有操作成功时统一返回结果数组。以下是其关键特性与典型应用场景的简要描述： 核心功能 1、并行执行接收一个 Promise 数组&…...

编程日记 2025/5/21 23:22:46

OpenVLA-OFT

TL;DR 2025 年斯坦福提出的 OpenVLA 工作的续作 OpenVLA-OFT，优化 VLA 能够有效适应新的机器人平台和任务，优化的技术主要有并行解码、动作块处理、连续动作、L1 回归和（可选的）FiLM 语言调节 Paper name Fine-Tuning Vision-La…...

编程日记 2025/5/6 19:23:09

2025“钉耙编程”中国大学生算法设计春季联赛（8）10031007

题目的意思很好理解找从最左边到最右边最短路（BFS） #include <bits/stdc.h> using namespace std; int a[510][510]; // 存储网格中每个位置是否有障碍（1表示有障碍，0表示无障碍） int v[510][510]; // 记录每…...

编程日记 2025/4/29 15:29:59

代码随想录算法训练营第六十一天 | floyd算法

Floyd 算法精讲题目链接：97. 小明逛公园文章讲解：代码随想录思想：本题是多源最短路，即求多个起点到多个终点的多条最短路径。用Floyd 算法。 Floyd 算法对边的权值正负没有要求，都可以处理，Floyd算法…...

编程日记 2025/5/22 8:12:08

[三分钟]web自动化测试（三）：selenium自动化测试常用函数(下)

文章目录 4.等待4.1 强制等待4.2 隐式等待4.3 显式等待 5.浏览器导航5.1 浏览器的前进、后退、刷新5.2 打开网站 6. 弹窗6.1 确认和取消6.2 输入信息 7. 文件上传 4.等待如果页面渲染的速度赶不上代码执行的速度，可能会因为渲染过慢出现自动化误报的问题。此时可…...

编程日记 2025/4/29 15:27:45

文档声明：HTML文档的基石

在前端开发的世界里，文档声明虽是一个看似不起眼的细节，却在网页的解析和渲染过程中扮演着至关重要的角色。今天，就让我们深入探讨文档声明的奥秘，揭开它背后的原理和重要性。一、文档声明的定义与作用文档声明，顾…...

编程日记 2025/5/11 1:41:40

光学涡旋干涉仪

一、什么是涡旋干涉仪？ 涡旋光束一般指电场含有螺旋相位因子exp(iℓθ)的光束，其中ℓ为拓扑荷数，θ为方位角，其波前为螺旋形，光束中心存在相位奇点，因此涡旋光束的光强轮廓是中心强度为零的圆环。早在1992…...

编程日记 2025/4/29 15:23:19

Wireshark快速入门--对启动的后端程序进行抓包

怎么对自己启动的后端程序进行抓包？ 1. 安装并启动 Wireshark 你要先从 Wireshark 官网下载对应系统的安装包，然后进行安装。安装完成后，启动该软件。可以快速入门可以参考博文：从零开始学 Wireshark：网络分析入门…...

编程日记 2025/4/29 15:21:05

ViTa-Zero：零样本视觉触觉目标 6D 姿态估计

25年4月来自Amazon 公司、Brown 大学和 Northestern 大学的论文“ViTa-Zero: Zero-shot Visuotactile Object 6D Pose Estimation”。目标 6D 姿态估计是机器人技术中的一项关键挑战，尤其对于操作任务而言。虽然先前结合视觉和触觉（视觉触觉&#xff0…...

编程日记 2025/5/16 8:33:33