JAVA练习355- 最小路径和

题目概览

给定一个包含非负整数的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.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= 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]; } }