04—最小路径和 【LeetCode64】
04—最小路径和 【LeetCode64】
吃猫的鱼Code
发布于 2023-07-24 18:29:17
发布于 2023-07-24 18:29:17
题目
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例一：
img
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。示例二：
输入：grid = [[1,2,3],[4,5,6]]
输出：12提示：
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 200
- 0 <= gridi <= 200
解题
解法一
思路
由于题中指出“每次只能向下或者向右移动一步。”，因此本题还是相对比较简单的。
首先定义一个数组dp[][]长度大小和题给数组相同，dp[i][j]数组中存储的是到达每个索引处的最短路径。通过循环可以将dp[][]填满。由于每次只能向下或者向右移动一步，因此第一列和第一行的可以优先快速被填充完，然后接下来再继续填充中间的数组即可。
解决
class Solution {
public int minPathSum(int[][] grid) {
//首先初始化定义一个和题给数组大小一样的数组，dp用来记录最短路径
int[][] dp = new int[grid.length][grid[0].length];
//第一个位置的路径是固定
dp[0][0] = grid[0][0];
//将第一列进行填充
for(int i=1;i结果
> 2023/07/14 14:36:58
解答成功:
执行耗时:2 ms,击败了92.29% 的Java用户
内存消耗:42.7 MB,击败了88.21% 的Java用户本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
相关产品与服务
对象存储
对象存储（Cloud Object Storage，COS）是由腾讯云推出的无目录层次结构、无数据格式限制，可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限，无需分区管理，适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。