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

2.5路径问题专题：LeetCode 64. 最小路径和

news 来源：原创 2025/9/8 11:18:05

动态规划解决最小路径和问题

1. 题目链接

LeetCode 64. 最小路径和

2. 题目描述

给定一个包含非负整数的 m x n 网格 grid，从网格的左上角出发，每次只能向右或向下移动一步，最终到达右下角。要求找到一条路径，使得路径上的数字总和最小。

3. 示例分析

示例输入：

grid = [[1,3,1],[1,5,1],[4,2,1]
]

输出：7
解释：最小路径为 1 → 3 → 1 → 1 → 1，路径和为 1 + 3 + 1 + 1 + 1 = 7。

4. 算法思路

动态规划（Dynamic Programming）

定义 dp[i][j] 表示从起点 (0,0) 到达位置 (i-1,j-1) 的最小路径和。为了简化边界条件的处理，将 dp 数组的维度扩展为 (m+1) x (n+1)，并初始化所有值为 INT_MAX。

状态转移方程

对于每个位置 (i, j)，其最小路径和由上方或左方的最小路径和决定：
dp[i][j] = grid[i-1][j-1] + min(dp[i-1][j], dp[i][j-1])
其中，grid[i-1][j-1] 是当前位置的值，dp[i-1][j] 是上方的路径和，dp[i][j-1] 是左方的路径和。

初始化
  • dp[0][1] = 0：设置一个虚拟起点 dp[0][1] 的值为0，使得起点 dp[1][1] 的值可以正确计算为 grid[0][0] + 0。
  • 其余位置初始化为 INT_MAX，表示尚未计算。

5. 边界条件与注意事项

  1. 单行或单列网格：当 m=1 或 n=1 时，路径是唯一的，直接累加所有元素即可。
  2. 索引转换：dp[i][j] 对应网格中的 grid[i-1][j-1]，需要注意索引偏移。
  3. 虚拟起点的作用：通过 dp[0][1] = 0 避免了在循环中单独处理起点 (1,1) 的初始化问题。
  4. 输入为空的情况：题目假设输入为非空网格，但实际代码中需注意 grid[0].size() 可能越界。

6. 代码实现

class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int m = grid.size(), n = grid[0].size();vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));dp[0][1] = 0; // 虚拟起点，用于初始化 dp[1][1]for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {dp[i][j] = grid[i - 1][j - 1] + min(dp[i - 1][j], dp[i][j - 1]);}}return dp[m][n];}
};

代码解释

  1. 初始化 dp 数组：通过 dp[0][1] = 0 使得起点 (1,1) 的值为 grid[0][0]。
  2. 填充 dp 数组：遍历每个位置，根据上方和左方的最小值更新当前路径和。
  3. 返回结果：最终结果存储在 dp[m][n]，表示到达右下角的最小路径和。

复杂度分析

  • 时间复杂度：O(mn)，遍历整个网格。
  • 空间复杂度：O(mn)，使用了 (m+1) x (n+1) 的 dp 数组。

通过动态规划方法，能够高效解决二维网格中的最小路径和问题，适用于机器人导航、资源分配等实际场景。

相关文章：

2.5路径问题专题：LeetCode 64. 最小路径和

动态规划解决最小路径和问题 1. 题目链接 LeetCode 64. 最小路径和 2. 题目描述 给定一个包含非负整数的 m x n 网格 grid&#xff0c;从网格的左上角出发&#xff0c;每次只能向右或向下移动一步&#xff0c;最终到达右下角。要求找到一条路径&#xff0c;使得路径上的数字…...

编程日记 2025/9/8 11:18:05

办公设备管理系统(springboot+ssm+jsp+maven)

基于springboot的办公设备管理系统(springbootssmjspmaven) 系统功能主要有&#xff1a; 欢迎页账号管理 管理员账号管理系统账号添加密码修改 普通管理员管理 用户管理用户添加用户查询 资产类型管理资产信息管理资产档案管理资产报表...

编程日记 2025/9/8 6:17:36

蓝桥杯2024JavaB组的一道真题的解析

文章目录 1.问题描述2.问题描述3.思路分析4.代码分析 1.问题描述 这个是我很久之前写的一个题目&#xff0c;当时研究了这个题目好久&#xff0c;发布了一篇题解&#xff0c;后来很多人点赞&#xff0c;我都没有意识到这个问题的严重性&#xff0c;我甚至都在怀疑自己&#xf…...

编程日记 2025/9/8 11:13:06

数据库--SQL

SQL&#xff1a;Structured Query Language&#xff0c;结构化查询语言 SQL是用于管理关系型数据库并对其中的数据进行一系列操作&#xff08;包括数据插入、查询、修改删除&#xff09;的一种语言 分类&#xff1a;数据定义语言DDL、数据操纵语言DML、数据控制语言DCL、事务处…...

编程日记 2025/9/8 11:10:06

SQL Server：Log Shipping 说明

目录标题 SQL Server Log Shipping与Oracle归档日志备份对比分析一、SQL Server Log Shipping的日志截断机制二、Oracle归档日志备份对比三、关键配置对比表四、最佳实践建议 如何修改和查看SQL Server默认备份配置防止自动删除&#xff1f;一、查看现有备份配置二、修改备份配…...

编程日记 2025/9/8 11:13:07

Zephyr实时操作系统初步介绍

一、概述 Zephyr是由Linux基金会托管的开源实时操作系统&#xff08;RTOS&#xff09;&#xff0c;专为资源受限的物联网设备设计。其核心特性包括模块化架构、跨平台兼容性、安全性优先以及丰富的连接协议支持。基于Apache 2.0协议&#xff0c;Zephyr允许商业和非商业用途的自…...

编程日记 2025/9/8 11:17:10

【大模型系列篇】大模型基建工程：基于 FastAPI 自动构建 SSE MCP 服务器 —— 进阶篇

&#x1f525;&#x1f525;&#x1f525; 上期 《大模型基建工程&#xff1a;基于 FastAPI 自动构建 SSE MCP 服务器》中我们使用fastapi-mcp自动挂载fastapi到mcp工具&#xff0c;通过源码分析和实践&#xff0c;我们发现每次sse请求又转到了内部fastapi RESTful api接口&…...

编程日记 2025/9/8 11:10:57

深度学习deeplearn3

# Jupyter Notebook魔法命令&#xff0c;用于在Notebook中内联显示图表 %matplotlib inline# 导入NumPy库&#xff0c;用于高效的数值计算 import numpy as np# 从matplotlib_inline库导入backend_inline模块&#xff0c;用于设置图表显示格式 from matplotlib_inline import b…...

编程日记 2025/9/8 1:34:06

（九）图形管线

一图说明问题 顶点数据->顶点着色器->细分着色器->几何着色器->光栅化->片元着色器->颜色混合 创建图形管线函数放在后面位置 void MyApplication::initVulkan() { createInstance(); createSurface(); pickPhysicalDevice(); createLogicalDevice(); cre…...

编程日记 2025/9/8 11:10:57

7-3 逆序的三位数

程序每次读入一个正3位数&#xff0c;然后输出按位逆序的数字。注意&#xff1a;当输入的数字含有结尾的0时&#xff0c;输出不应带有前导的0。比如输入700&#xff0c;输出应该是7。 输入格式&#xff1a; 每个测试是一个3位的正整数。 输出格式&#xff1a; 输出按位逆序…...

编程日记 2025/9/8 11:17:10

git从历史版本创建新分支或标签

git从某个历史版本创建标签 # 查看历史版本 git log git tag tag-v1.0 780e2a7fc714faf388ba71git从某个分支的指定历史版本中创建新分支 # 查看历史版本 git log # 从历史分支创建标签 git checkout -b new-branch 780e2a7fc714faf388ba71...

编程日记 2025/9/8 11:13:35

HTML 音频（Audio）学习笔记

一、HTML 音频概述 在 HTML 中&#xff0c;音频可以通过多种方式播放&#xff0c;但要确保音频在不同浏览器和设备上都能正常播放&#xff0c;需要掌握一些技巧。HTML5 引入了 <audio> 元素&#xff0c;为音频播放提供了一种标准方法&#xff0c;但在 HTML4 中&#xff…...

编程日记 2025/9/8 11:13:36

五种音频器件综合对比——《器件手册--音频器件》

目录 音频器件 简述 1. 扬声器&#xff08;Speakers&#xff09; 2. 麦克风&#xff08;Microphones&#xff09; 3. 放大器&#xff08;Amplifiers&#xff09; 4. 音频接口&#xff08;Audio Interfaces&#xff09; 5. 音频处理器&#xff08;Audio Processors&#xff09…...

编程日记 2025/9/8 11:15:34

数据结构复习（单调栈，单调队列，KMP，manacher，tire，字符串哈希）

单调栈&#xff1a; 介绍&#xff1a; 单调栈用于解决"寻找每个元素左侧/右侧第一个比它小/大的元素"类问题。栈中元素保持单调性&#xff0c;时间复杂度O(n)。 维护一个严格递增栈。对于每个元素a[i]&#xff0c;不断弹出栈顶比a[i]大的元素&#xff0c;剩下的栈顶即…...

编程日记 2025/9/8 11:15:33

(学习总结32)Linux 基础 IO

Linux 基础 IO 一、什么是 " 文件 "二、C 文件接口打开文件写文件读文件其它介绍 三、系统文件 I/O传递标志位系统接口写文件系统接口读文件部分系统调用接口介绍打开文件函数 open关闭文件函数 close写入文件函数 write读取文件函数 read 文件描述符 fdfd 0 & 1…...

编程日记 2025/9/8 11:16:12

操作系统（一）：概念及主流系统全分析

目录 一.操作系统是什么 二.操作系统的分类 2.1 按应用场景分类 2.2 按实时性分类 2.3 按内核架构分类 2.4 按用户与任务分类 三.主流操作系统比较 四.未来趋势 一.操作系统是什么 操作系统&#xff08;Operating System, OS&#xff09;是计算机系统的核心软件&#x…...

编程日记 2025/9/8 11:10:07

三、GPIO

一、GPIO简介 GPIO&#xff08;General Purpose Input Output&#xff09;通用输入输出口GPIO引脚电平&#xff1a;0V&#xff08;低电平&#xff09;~3.3V&#xff08;高电平&#xff09;&#xff0c;部分引脚可容忍5V 容忍5V&#xff0c;即部分引脚输入5V的电压&#xff0c;…...

编程日记 2025/9/8 11:14:26

Ceph异地数据同步之-RBD异地同步复制（上）

#作者&#xff1a;闫乾苓 文章目录 前言基于快照的模式&#xff08;Snapshot-based Mode&#xff09;工作原理单向同步配置步骤单向同步复制测试双向同步配置步骤双向同步复制测试 前言 Ceph的RBD&#xff08;RADOS Block Device&#xff09;支持在两个Ceph集群之间进行异步镜…...

编程日记 2025/9/8 11:14:28

fastapi完全离线环境（无外网）的访问Swagger所做特殊处理

在互联网环境中&#xff0c;只要 启动FastAPI 服务运行在本地机器上&#xff0c;访问 http://localhost:8000/docs&#xff08;Swagger UI&#xff09;就可以访问到Swagger界面&#xff0c;但是在完全离线环境&#xff08;无外网&#xff09;下如何访问Swagger页面呢&#xff1…...

编程日记 2025/9/4 6:47:22

在网络中加入预训练的多层感知机（MLP）有什么作用？

在网络中加入预训练的多层感知机&#xff08;MLP&#xff09;通常是为了引入先验知识、提升特征表示能力或dropout&#xff0c;具体作用取决于MLP的设计和预训练任务。以下是常见的应用场景和优势&#xff1a; 1. 特征融合与迁移学习:预训练的MLP可以作为特征提取器&#xff0…...

编程日记 2025/9/3 19:53:54

3.2/Q2，GBD数据库最新文章解读

文章题目&#xff1a;Temporal trends in the burden of vertebral fractures caused by falls in China and globally from 1990 to 2021: a systematic analysis of the Global Burden of Disease Study 2021 DOI&#xff1a;10.1186/s13690-025-01500-y 中文标题&#xff1a…...

编程日记 2025/9/5 21:11:34

机器学习的一百个概念（9）学习曲线

前言 本文隶属于专栏《机器学习的一百个概念》&#xff0c;该专栏为笔者原创&#xff0c;引用请注明来源&#xff0c;不足和错误之处请在评论区帮忙指出&#xff0c;谢谢&#xff01; 本专栏目录结构和参考文献请见[《机器学习的一百个概念》 ima 知识库 知识库广场搜索&…...

编程日记 2025/9/7 19:04:19

浅谈Tomcat数据源连接池

目录 为什么需要JDBC连接池 Tomcat JDBC Pool 相关参数 1. 基本配置 2. 连接池大小控制 3. 连接验证与测试 4. 空闲连接回收 5. 连接泄漏与超时 Tomcat JDBC Pool 源码分析&#xff08;tomcat 8.5.3&#xff09; DataSourceFactory DataSource ConnectionPool Pool…...

编程日记 2025/9/5 3:26:56

Techub 财报解读：Circle 冲刺 IPO，但收入增长难掩利润困局

作者&#xff1a;Techub 财报解读 撰文&#xff1a;Yangz&#xff0c;Techub News 4 月 1 日&#xff0c;Circle 向美国证券交易委员会&#xff08;SEC&#xff09;提交 S-1 文件&#xff0c;计划进行首次公开募股&#xff08;IPO&#xff09;&#xff0c;股票代码为 CRCL&…...

编程日记 2025/9/6 10:57:55

C++中的链表操作

在C中&#xff0c;链表是一种常见的数据结构&#xff0c;它由一系列节点组成&#xff0c;每个节点包含数据部分和指向下一个节点的指针。C标准库&#xff08;STL&#xff09;中提供了std::list和std::forward_list两种链表实现&#xff0c;分别对应双向链表和单向链表。此外&am…...

编程日记 2025/9/3 6:11:51

Vue2 生命周期

文章目录 前言&#x1f504; Vue2 生命周期流程&#xff08;8个核心钩子&#xff09;&#x1f4dd; 代码中典型用法示例一、您的描述验证二、完整生命周期代码示例三、关键阶段行为说明&#x1f50d; 常见问题 前言 提示&#xff1a;以下是本篇文章正文内容&#xff0c;下面案…...

编程日记 2025/9/3 17:58:30

2007-2022年 上市公司政府补助数据 -社科数据

上市公司政府补助数据&#xff08;2007-2022年&#xff09;-社科数据https://download.csdn.net/download/paofuluolijiang/90028547 https://download.csdn.net/download/paofuluolijiang/90028547 政府补助是指政府为支持企业发展&#xff0c;提供的资金或资源支持。对于上市…...

编程日记 2025/9/5 19:27:42

设计心得——状态机

一、状态机 在设计一些与硬件交互或者游戏等开发中&#xff0c;经常会听到状态机&#xff08;State Machines&#xff09;这个字眼&#xff0c;而在设计模式&#xff08;GoF&#xff09;中&#xff0c;又经常听到状态模式这个概念&#xff0c;它们之间有什么联系和不同呢&…...

编程日记 2025/9/8 0:13:54

python match case语法

学习路线&#xff1a;B站 普通的if判断 def if_traffic_light(color):if color red:return Stopelif color yellow:return Slow downelif color green:return Goelse:return Invalid colorprint(if_traffic_light(red)) # Output: Stop print(if_traffic_light(yellow)) …...

编程日记 2025/9/6 15:56:00

Lua中协程相关函数使用详解

目录 1. coroutine.create(f)2. coroutine.resume(co [, val1, ...])3. coroutine.yield([val1, ...])4. coroutine.status(co)5. coroutine.wrap(f)6. coroutine.running()7. coroutine.isyieldable()协程状态转换示例总结 Lua 中的协程&#xff08;coroutine&#xff09;提供…...

编程日记 2025/9/3 19:44:52

代码拟有感

最近的日子像被按了0.5倍速播放键。腱鞘炎让手腕转动时发出咯吱声&#xff0c;尾骨的钝痛让久坐变成酷刑&#xff0c;落枕的脖子和酸胀的手臂组成了“疼痛交响乐”——这些隐秘的、持续的身体抗议&#xff0c;让原本枯燥的代码练习变成了一场生理与意志的拉锯战。 我盯着屏幕苦…...

编程日记 2025/9/5 12:22:35

《实战AI智能体》MCP对Agent有哪些好处

首先MCP为Agent提供了标准化的方式来接入各种工具和数据源，无论是本地运行的工具，例如通过stdio服务器，还是远程托管的服务HTTP over SSE服务， Agent都可以通过统一的接口与它们进行交互，极大扩展了第三方工具库。 例如，在金融领域，Agent 可以接入股票分析的MCP工具。当…...

编程日记 2025/9/8 6:26:55

maptalks获取所有图层并把图层按照zIndex排序

maptalks获取所有图层并把图层按照zIndex排序 获取所有图层 通过调用 map.getLayers() 可以返回当前地图上所有的图层集合。此方法会返回一个数组形式的结果&#xff0c;其中包含了地图上的每一个图层层级对象。 图层属性中的 ZINDEX 每种图层类型&#xff08;如矢量图层、…...

编程日记 2025/9/3 13:11:50

GUI-Guider 按钮按下 选项卡 右移动一个，到最右边停下

extern lv_ui guider_ui; // 在文件顶部添加// 在按钮事件中使用&#xff1a; lv_obj_t * tabview guider_ui.screen_tabview_1; // 替换为你的实际 TabView 名称 uint16_t current lv_tabview_get_tab_act(tabview); lv_tabview_set_act(tabview, current 1, LV_ANIM_ON); …...

编程日记 2025/9/7 11:16:32

让AI再次伟大-MCP-Client开发指南

&#x1f44f;作者简介&#xff1a;大家好&#xff0c;我是爱吃芝士的土豆倪&#xff0c;24届校招生Java选手&#xff0c;很高兴认识大家&#x1f4d5;系列专栏&#xff1a;Spring原理、JUC原理、Kafka原理、分布式技术原理、数据库技术、JVM原理、AI应用&#x1f525;如果感觉…...

编程日记 2025/9/6 21:47:18

sql工具怎么选？

为什么大多数主流工具又贵又难用&#xff1f; 有没有一款免费好用的sql工具&#xff1f; 像大多人朋友常用的sql工具&#xff0c;应该都遇到过这种情况&#xff0c; 用着用着收到了来自品牌方的律师函&#xff0c; 或者处理数据经常卡死&#xff0c; 再或者不支持国产数据库…...

编程日记 2025/9/3 21:11:21

video标签播放mp4格式视频只有声音没有图像的问题

video标签播放mp4格式视频只有声音没有图像的问题 这是由于视频格式是hevc(H265)编码的&#xff0c;这种编码格式视频video播放有问题主要是由于以下两种原因导致的&#xff1a; 1、浏览器没有开启硬加速模式&#xff1a; 开启方法&#xff08;以谷歌浏览器为例&#xff09;&a…...

编程日记 2025/9/3 12:00:55

问题解决：glog中的LOG(INFO)与VLOG无法打印

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。 本作品 (李兆龙 博文, 由 李兆龙 创作)&#xff0c;由 李兆龙 确认&#xff0c;转载请注明版权。 文章目录 MotivationProcess glog版本为&#xff1a;https://github.com/google/glog/archive/…...

编程日记 2025/9/6 3:16:35

【第2月 day16】Matplotlib 散点图与柱状图

好的&#xff01;以下是针对初学者的 Matplotlib 散点图与柱状图 学习内容&#xff0c;用简单易懂的语言和示例讲解&#xff1a; 一、散点图&#xff08;Scatter Plot&#xff09; 作用&#xff1a;展示两个变量之间的关系&#xff08;如相关性、分布等&#xff09;。 1. 核心…...

编程日记 2025/9/8 8:10:06

汽车 HMI 设计的发展趋势与设计要点

一、汽车HMI设计的发展历程与现状 汽车人机交互界面&#xff08;HMI&#xff09;设计经历了从简单到复杂、从单一到多元的演变过程。2012年以前&#xff0c;汽车HMI主要依赖物理按键进行操作&#xff0c;交互方式较为单一。随着特斯拉Model S的推出&#xff0c;触控屏逐渐成为…...

编程日记 2025/9/6 12:01:57

Vue 3 中按照某个字段将数组分成多个数组

方法一&#xff1a;使用 reduce 方法 const originalArray [{ id: 1, category: A, name: Item 1 },{ id: 2, category: B, name: Item 2 },{ id: 3, category: A, name: Item 3 },{ id: 4, category: C, name: Item 4 },{ id: 5, category: B, name: Item 5 }, ];const grou…...

编程日记 2025/9/8 1:34:09

06-Spring 中的事件驱动机制

Spring 中的事件驱动机制&#xff08;ApplicationEvent 源码解析&#xff09; 本小结主要总结Spring的事件&#xff0c;如果对于观察者模式比较熟悉的话&#xff0c;理解这个应该不难。 这块涉及的面试题相对简单&#xff0c;主要还是以日常使用为主。 另外在Spring的源码中也运…...

编程日记 2025/9/1 9:49:04

Python学习笔记（8）关于列表内置函数和多维列表

列表访问计数 索引直接访问 index()#获得首次出现指定元素的索引 index(value,[start,[end]] #控制搜索索引范围 counr()#获得指定元素在列表中出现的次数 len()#返回列表长度 成员资格判断 incount()返回0&#xff0c;代表不存在 列表切片 slice[起始偏移量 start:终止…...

编程日记 2025/8/28 22:22:58

【算法学习计划】回溯 -- 递归

目录 leetcode 面试题08.06.汉诺塔问题 leetcode 21.合并两个有序链表 leetcode 206.反转链表 leetcode 24.两两交换链表中的节点 leetcode 50. Pow(x, n) 本篇文章将是我们回溯专题的第一篇文章&#xff0c;在这里我先浅浅讲一下什么是回溯 其实就是递归&#xff0c;只不…...

编程日记 2025/9/8 0:50:17

Unity中 JobSystem使用整理

Unity 的JobSystem允许创建多线程代码&#xff0c;以便应用程序可以使用所有可用的 CPU 内核来执行代码&#xff0c;这提供了更高的性能&#xff0c;因为您的应用程序可以更高效地使用运行它的所有 CPU 内核的容量&#xff0c;而不是在一个 CPU 内核上运行所有代码。 可以单独使…...

编程日记 2025/9/5 6:15:33

【从零实现Json-Rpc框架】- 项目实现 - 服务端主题实现及整体封装

&#x1f4e2;博客主页&#xff1a;https://blog.csdn.net/2301_779549673 &#x1f4e2;博客仓库&#xff1a;https://gitee.com/JohnKingW/linux_test/tree/master/lesson &#x1f4e2;欢迎点赞 &#x1f44d; 收藏 ⭐留言 &#x1f4dd; 如有错误敬请指正&#xff01; &…...

编程日记 2025/9/6 18:53:04

JavaScript基础-移动端常用开发框架

随着移动互联网的发展&#xff0c;越来越多的应用和服务需要支持移动设备。为了提高开发效率和用户体验&#xff0c;开发者们依赖于一些成熟的JavaScript框架来构建响应迅速、功能丰富的移动Web应用。本文将介绍几款广泛使用的移动端开发框架&#xff0c;并通过具体的示例展示它…...

编程日记 2025/9/6 18:57:38

Tree - Shaking

Vue 3 的 Tree - Shaking 技术详解 Tree - Shaking 是一种在打包时移除未使用代码的优化技术&#xff0c;在 Vue 3 中&#xff0c;Tree - Shaking 发挥了重要作用&#xff0c;有效减少了打包后的代码体积&#xff0c;提高了应用的加载性能。以下是对 Vue 3 中 Tree - Shaking …...

编程日记 2025/9/7 19:35:22

VSCode历史版本的下载安装

VSCode历史版本的下载安装 文章目录 VSCode历史版本的下载安装VSCode安装下载历史版本地址查询VSCode历史版本的 commit id 安装参考资料 VSCode安装 Windows版本&#xff1a;Windows10VSCode版本&#xff1a;VScode1.65.0&#xff08;64位User版本&#xff09;本文编写时间&a…...

编程日记 2025/9/2 11:13:36

Websoft9分享：在数字化转型中选择开源软件可能遇到的难题

引言&#xff1a;中小企业数字化转型的必由之路 全球94.57%的企业已采用开源软件&#xff08;数据来源&#xff1a;OpenLogic 2024报告)&#xff0c;开源生态估值达8.8万亿美元。中小企业通过开源软件构建EPR系统、企业官网、数据分析平台等&#xff0c;可节省80%软件采购成本。…...

编程日记 2025/9/7 17:40:28