题目概览给定一个包含非负整数的mxn网格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.lengthn grid[i].length1 m, n 2000 grid[i][j] 200来源64. 最小路径和 - 力扣LeetCode解题分析方法动态规划当前位置的最短路径就是看上面路径和左边路径的最小值 加上当前值状态转移方程为dp[ i ] [ j ] min { dp[ i - 1 ] [ j ], dp[ i ] [ j - 1 ] } grid[ i ] [ j ]由于 grid 我们查完后后续不在使用因此可以用 grid 代替 dp降低空间复杂度。时间复杂度O(mn)空间复杂度O(1)class Solution { public int minPathSum(int[][] grid) { int m grid.length, n grid[0].length; for (int i 1; i m; i) { grid[i][0] grid[i-1][0]; } for (int j 1; j n; j) { grid[0][j] grid[0][j-1]; } for (int i 1; i m; i) { for (int j 1; j n; j) { grid[i][j] Math.min(grid[i-1][j], grid[i][j-1]); } } return grid[m-1][n-1]; } }