064.最小路径和
作者：沉默王二
发布时间：2022-11-29T10:23:22.470+0800
本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记，数学表达公式也能显示出来），访问地址和密码：https://t.zsxq.com/6iuzn6I
064.最小路径和
题意
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
**说明：**每次只能向下或者向右移动一步。
难度
中等
示例
示例1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：
输入：grid = [[1,2,3],[4,5,6]]
分析
本题还是可以用 动态规划 来解决，因为这题和前面两题—— 062.不同路径 、063.不同路径 II 有一个共同之处，每个位置都只能由它的上方或者是左边转移而来。
同样，我们还是利用f[i][j]来表示走到第i行第j列最少的数字总和。
基于这样子的思想我们可以写出如下的动态转移方程：
依照该动态转移方程，我们可以写出如下的代码。
class Solution {
for(int i = 0;i < grid.length;i++) { for (int j = 0; j < grid[0].length; j++) { if (i == 0 && j == 0) {continue;} if (i == 0) {grid[i][j] += grid[i][j - 1];} else if (j == 0) {grid[i][j] += grid[i - 1][j];} else {grid[i][j] += Math.min(grid[i][j - 1], grid[i - 1][j]);} } } return grid[grid.length - 1][grid[0].length - 1]; }}
代码中直接利用了grid[][]来替代f[][]，来节省空间。
最终的时间复杂度为，空间复杂度也为。
总结
这类在网格图上行走，并且要求最小值/最大值的题目，通常可以利用 动态规划 来解决，我们首先将该题的 状态（本题中即网格图的位置） 提取出来，再观察这个状态是由那些状态转移而来的，是怎么转移的，从而总结出动态转移方程，最后便可以写出代码了。
力扣链接：https://leetcode.cn/problems/minimum-path-sum/
一步一个脚印
不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。
PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。
一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 1000 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！
本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记，数学表达公式也能显示出来），访问地址和密码：https://t.zsxq.com/6iuzn6I
064.最小路径和
题意
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
**说明：**每次只能向下或者向右移动一步。
难度
中等
示例
示例1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：
输入：grid = [[1,2,3],[4,5,6]]
分析
本题还是可以用 动态规划 来解决，因为这题和前面两题—— 062.不同路径 、063.不同路径 II 有一个共同之处，每个位置都只能由它的上方或者是左边转移而来。
同样，我们还是利用f[i][j]来表示走到第i行第j列最少的数字总和。
基于这样子的思想我们可以写出如下的动态转移方程：
依照该动态转移方程，我们可以写出如下的代码。
class Solution {
for(int i = 0;i < grid.length;i++) { for (int j = 0; j < grid[0].length; j++) { if (i == 0 && j == 0) {continue;} if (i == 0) {grid[i][j] += grid[i][j - 1];} else if (j == 0) {grid[i][j] += grid[i - 1][j];} else {grid[i][j] += Math.min(grid[i][j - 1], grid[i - 1][j]);} } } return grid[grid.length - 1][grid[0].length - 1]; }}
代码中直接利用了grid[][]来替代f[][]，来节省空间。
最终的时间复杂度为，空间复杂度也为。
总结
这类在网格图上行走，并且要求最小值/最大值的题目，通常可以利用 动态规划 来解决，我们首先将该题的 状态（本题中即网格图的位置） 提取出来，再观察这个状态是由那些状态转移而来的，是怎么转移的，从而总结出动态转移方程，最后便可以写出代码了。
力扣链接：https://leetcode.cn/problems/minimum-path-sum/
一步一个脚印
不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。
PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。
一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 1000 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！
本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记，数学表达公式也能显示出来），访问地址和密码：https://t.zsxq.com/6iuzn6I
064.最小路径和
题意
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
**说明：**每次只能向下或者向右移动一步。
难度
中等
示例
示例1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：
输入：grid = [[1,2,3],[4,5,6]]
分析
本题还是可以用 动态规划 来解决，因为这题和前面两题—— 062.不同路径 、063.不同路径 II 有一个共同之处，每个位置都只能由它的上方或者是左边转移而来。
同样，我们还是利用f[i][j]来表示走到第i行第j列最少的数字总和。
基于这样子的思想我们可以写出如下的动态转移方程：
依照该动态转移方程，我们可以写出如下的代码。
class Solution {
for(int i = 0;i < grid.length;i++) { for (int j = 0; j < grid[0].length; j++) { if (i == 0 && j == 0) {continue;} if (i == 0) {grid[i][j] += grid[i][j - 1];} else if (j == 0) {grid[i][j] += grid[i - 1][j];} else {grid[i][j] += Math.min(grid[i][j - 1], grid[i - 1][j]);} } } return grid[grid.length - 1][grid[0].length - 1]; }}
代码中直接利用了grid[][]来替代f[][]，来节省空间。
最终的时间复杂度为，空间复杂度也为。
总结
这类在网格图上行走，并且要求最小值/最大值的题目，通常可以利用 动态规划 来解决，我们首先将该题的 状态（本题中即网格图的位置） 提取出来，再观察这个状态是由那些状态转移而来的，是怎么转移的，从而总结出动态转移方程，最后便可以写出代码了。
力扣链接：https://leetcode.cn/problems/minimum-path-sum/
一步一个脚印
不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。
PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。
一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 1000 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！
知识星球
扫码加入星球
查看更多优质内容
https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412