新闻详情

新闻详情

首页 / 资讯中心 / 详情

LeetCode 64:最小路径和

发布时间:2026/11/16 13:24:03来源:尧图网络
LeetCode 64:最小路径和
LeetCode 64最小路径和1. 题目核心给定一个m × n的非负整数网格grid从左上角(0,0)出发到右下角(m-1,n-1)每次只能向右 向下要求找到一条路径使经过的所有数字之和最小并返回这个最小路径和。例如1 3 1 1 5 1 4 2 1最优路径1 → 3 → 1 ↓ 1 ↓ 1路径和1 3 1 1 1 72. 思路一DFS / 枚举所有路径从(0,0)开始每个位置尝试向右 向下一直走到右下角计算每条路径的数字总和最后取最小值。这种方法逻辑直观但会产生大量重复搜索例如同一个位置(i,j)可以通过很多不同路线到达而到达之后的后续路线会被重复计算因此效率较低。3. 思路二动态规划 DP3.1 DP 状态定义定义dp[i][j]表示从左上角(0,0)走到(i,j)时可以得到的最小路径和。注意这题和上一题“不同路径 II”很像但含义完全不同不同路径 dp[i][j] 到达当前位置有多少条路径 最小路径和 dp[i][j] 到达当前位置的最小数字总和3.2 为什么只看上面和左边机器人只能向右 向下所以想走到(i,j)最后一步只能来自上面(i-1,j) 左边(i,j-1)假设从上面到达时最小路径和 10 从左边到达时最小路径和 7 当前格子的值 3显然应该选择左边7 3 10而不是10 3 13所以dp[i][j] min(dp[i - 1][j], dp[i][j - 1]) grid[i][j];3.3 为什么这里用min上一题却用上一题“不同路径”求的是一共有多少种方案因此dp[i][j] dp[i - 1][j] dp[i][j - 1];这题求的是所有方案中哪一个代价最小所以dp[i][j] min(dp[i - 1][j], dp[i][j - 1]) grid[i][j];可以记求方案总数 → 求最大值 → max 求最小值 → min4. 初始化4.1 起点到达起点(0,0)什么地方都不用走因此路径和就是当前格子的值dp[0][0] grid[0][0];4.2 第一列第一列的格子只能从上面走下来(0,0) ↓ (1,0) ↓ (2,0)所以dp[i][0] dp[i - 1][0] grid[i][0];例如grid 1 1 4那么dp 1 2 64.3 第一行第一行只能一直向右(0,0) → (0,1) → (0,2)所以dp[0][j] dp[0][j - 1] grid[0][j];5. 示例完整推导对于grid 1 3 1 1 5 1 4 2 1初始化起点dp 1 ? ? ? ? ? ? ? ?初始化第一行dp[0][0] 1 dp[0][1] 1 3 4 dp[0][2] 4 1 5得到1 4 5 ? ? ? ? ? ?初始化第一列dp[1][0] 1 1 2 dp[2][0] 2 4 6得到1 4 5 2 ? ? 6 ? ?计算(1,1)min(上面4, 左边2) 5 2 5 7计算(1,2)min(上面5, 左边7) 1 5 1 6计算(2,1)min(上面7, 左边6) 2 6 2 8计算(2,2)min(上面6, 左边8) 1 6 1 7最终 DP1 4 5 2 7 6 6 8 7因此答案 dp[2][2] 76. C二维 DP你截图中的思路和代码就是这个标准解法。class Solution { public: int minPathSum(vectorvectorint grid) { int m grid.size(); int n grid[0].size(); vectorvectorint dp(m, vectorint(n, 0)); dp[0][0] grid[0][0]; // 初始化第一列 for (int i 1; i m; i) { dp[i][0] dp[i - 1][0] grid[i][0]; } // 初始化第一行 for (int j 1; j n; j) { dp[0][j] dp[0][j - 1] grid[0][j]; } // 状态转移 for (int i 1; i m; i) { for (int j 1; j n; j) { dp[i][j] min(dp[i - 1][j], dp[i][j - 1]) grid[i][j]; } } return dp[m - 1][n - 1]; } };7. Java二维 DPJava 使用的是完全相同的动态规划思路。class Solution { public int minPathSum(int[][] grid) { int m grid.length; int n grid[0].length; int[][] dp new int[m][n]; dp[0][0] grid[0][0]; // 初始化第一列 for (int i 1; i m; i) { dp[i][0] dp[i - 1][0] grid[i][0]; } // 初始化第一行 for (int j 1; j n; j) { dp[0][j] dp[0][j - 1] grid[0][j]; } // 状态转移 for (int i 1; i m; i) { for (int j 1; j n; j) { dp[i][j] Math.min(dp[i - 1][j], dp[i][j - 1]) grid[i][j]; } } return dp[m - 1][n - 1]; } }8. Java 语法解释8.1 二维数组int[][] grid对应 Cvectorvectorint grid8.2 获取行数和列数Javaint m grid.length; int n grid[0].length;Cint m grid.size(); int n grid[0].size();Java 数组使用.length没有括号。8.3 创建二维数组int[][] dp new int[m][n];表示创建一个m × n的二维整数数组默认所有元素初始化为0。8.4Math.minJavaMath.min(a, b)对应 Cmin(a, b)所以dp[i][j] Math.min(dp[i - 1][j], dp[i][j - 1]) grid[i][j];就是选择从上面和左边过来时路径和更小的那一个再加当前格子的值。9. Python二维 DPPython 同样使用相同的 DP。class Solution: def minPathSum(self, grid): m len(grid) n len(grid[0]) dp [[0] * n for _ in range(m)] dp[0][0] grid[0][0] # 初始化第一列 for i in range(1, m): dp[i][0] dp[i - 1][0] grid[i][0] # 初始化第一行 for j in range(1, n): dp[0][j] dp[0][j - 1] grid[0][j] # 状态转移 for i in range(1, m): for j in range(1, n): dp[i][j] ( min(dp[i - 1][j], dp[i][j - 1]) grid[i][j] ) return dp[m - 1][n - 1]10. Python 语法解释10.1 获取二维数组大小m len(grid)n len(grid[0])len(grid)是行数len(grid[0])是列数。10.2 创建二维数组dp [[0] * n for _ in range(m)]例如m 3 n 3得到[ [0,0,0], [0,0,0], [0,0,0] ]10.3 Python 的minmin(a, b)直接得到两个数中更小的一个。10.4range(1, m)for i in range(1, m):表示i 1,2,...,m-1对应 Cfor (int i 1; i m; i)11. 空间优化一维 DP因为dp[i][j]只依赖上面 dp[i-1][j] 左边 dp[i][j-1]所以可以只保存一行。使用dp[j]表示当前处理到第j列时的最小路径和。更新前dp[j] 上面那个格子的最小路径和而dp[j-1] 当前行左边格子的最小路径和所以dp[j] min(dp[j], dp[j - 1]) grid[i][j];空间复杂度可以从O(m × n)降低到O(n)12. C一维空间优化class Solution { public: int minPathSum(vectorvectorint grid) { int m grid.size(); int n grid[0].size(); vectorint dp(n, 0); dp[0] grid[0][0]; // 初始化第一行 for (int j 1; j n; j) { dp[j] dp[j - 1] grid[0][j]; } for (int i 1; i m; i) { // 当前行第一列只能从上面来 dp[0] grid[i][0]; for (int j 1; j n; j) { dp[j] min(dp[j], dp[j - 1]) grid[i][j]; } } return dp[n - 1]; } };13. 复杂度二维 DP时间复杂度O(m × n) 空间复杂度O(m × n)一维 DP时间复杂度O(m × n) 空间复杂度O(n)14. 与 LeetCode 63 的联系两道题几乎是同一个网格 DP 模板。LeetCode 63不同路径 II求有多少条路线所以dp[i][j] dp[i - 1][j] dp[i][j - 1];LeetCode 64最小路径和求哪条路线数字之和最小所以dp[i][j] min(dp[i - 1][j], dp[i][j - 1]) grid[i][j];它们共同的地方都是当前位置只能从 上面 左边 过来区别只是题目问的东西不同统计所有方案 → 相加 选最优方案 → min/max15. 核心记忆DP 定义dp[i][j] 从左上角走到 (i,j) 所能得到的最小路径和初始化dp[0][0] grid[0][0]; dp[i][0] dp[i - 1][0] grid[i][0]; dp[0][j] dp[0][j - 1] grid[0][j];状态转移dp[i][j] min(dp[i - 1][j], dp[i][j - 1]) grid[i][j];最后只记一句到当前格子的最小路径和 上面和左边两个来源中更小的路径和 当前格子的数字。
网站建设高端定制企业官网
RELATED

相关资讯

更多精彩内容,欢迎继续阅读

较早相关资讯

最新相关资讯

【外设】之大彩串口显示屏 2026/11/15 4:54:16

【外设】之大彩串口显示屏

大彩串口屏初步使用 1 .官网下载 STM32 屏幕 GUI 设计资料 http://www.gz-dc.com/category/typeid/4112 找到 STM32 Keil 工程,移植相关代码因项目而异进行移植,由于项目简单,本人只对用到的指令接口进行修改。 比如:注意事项&…

阅读更多 →
无法下载Windows系统iso文件 2026/11/15 2:04:12

无法下载Windows系统iso文件

当我遇到这个问题的时候,我打开了一个网站: 登录 然后我打算下载的时候: 突然那个官方的连接就可以下载了:

阅读更多 →
【清华代码熊】DeepSeek V4.1 Flash 后训练详解 2026/11/14 10:11:15

【清华代码熊】DeepSeek V4.1 Flash 后训练详解

📌 上期解析了 DeepSeek V4.1 Flash 模型架构改进,本期解析 DeepSeek V4.1 Flash 预训练/后训练技术: 🌟 预训练:45T 文本 多模态混合语料、直接训练 sparse attention(取消 DeepSeek V4 的 dense 冷启动&…

阅读更多 →
Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ... 2026/11/16 6:47:19

Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ...

文章主要内容和创新点 主要内容 本文聚焦于多模态大语言模型(MLLM)强化学习(RL)训练中的效率问题,提出了一个名为Shuffle-R1的框架。研究发现,当前RL训练存在两个关键缺陷: 优势值坍缩(Advantage Collapsing):批次中大多数优势值集中在零附近,导致有效梯度信号被淹…

阅读更多 →
PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction 2026/11/14 16:35:50

PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction

一、文章主要内容总结 本文聚焦于利用大型语言模型(LLMs)实现个人身份信息(PII)脱敏的研究,旨在解决传统脱敏方法(如基于规则的系统、领域特定命名实体识别(NER)模型)泛化能力差、跨格式/跨语境适应性弱的问题。 研究通过全面评估多种LLM架构(包括密集型LLM(D-LLM…

阅读更多 →
LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model 2026/11/15 4:06:36

LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model

文章主要内容和创新点 主要内容 本文聚焦于二进制图像-文本相关性评估任务(判断图像与文本“相关”或“不相关”),针对该任务中文本格式多样、相关性定义随场景变化等挑战,提出了基于多模态大语言模型(MLLM)的解决方案LLaVA-RE。 模型设计:LLaVA-RE基于LLaVA 1.5架构,…

阅读更多 →

今日资讯

本周资讯

本月资讯

看完文章仍有疑问?

联系尧图顾问,获取一对一建站咨询

立即免费咨询 📞 400-888-8888
📞 ✉