题目连接

示例

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：一个机器人每次只能向下或者向右移动一步。
image.png

示例 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

解题思路

朴实无华的动态规划解法。

考虑到一直沿着边缘走直线的权重是唯一的，因为机器人每次只能向下或向右走，不存在绕路的可能（如：图示中1-3-1、1-1-4，它们有唯一确定的权重1-4-5、1-2-6）。
优先确定了这些位置的权重作为初始状态之后，就可以利用动态规划的状态转移方程
dp[i][j] = min(dp[i-1][j],dp[i][j-1])+grid[i][j];
即上方、左边两个位置的权重最小值加上自身权重作为这个位置的权重。

如：对于5，上方3的权重是4，左边1的权重是2。5的权重就是2+5=7
最后返回右下角的最终权重（就是最小路径长度）

创建二维数组 dp，与原始网格的大小相同，dp[i][j] 表示从左上角出发到 (i,j)位置的最小路径和。显然，dp[0][0]=grid[0][0]。对于 dp 中的其余元素，通过以下状态转移方程计算元素值。

  • 当 i>0且 j=0 时，dp[i][0]=dp[i−1][0]+grid[i][0]。
  • 当 i=0且 j>0 时，dp[0][j]=dp[0][j−1]+grid[0][j]。
  • 当 i>0且 j>0 时，dp[i][j]=min(dp[i−1][j],dp[i][j−1])+grid[i][j]。

最后得到dp[m−1][n−1] 的值即为从网格左上角到网格右下角的最小路径和。

代码

  1. package wg.interview;
  2. public class MinPathSum {
  3. // 最短路径和
  5.     public static void main(String[] args) {
  6.         int[][] nm = {{3,1,0,2},{4,3,2,1},{5,2,1,0},{1,2,3,4},{0,0,0,1}};
  7.         System.out.println(MinPathSum.minPathSum(nm));
  8.     }
  10.     public static int minPathSum(int[][] grid) {
  11.         if (grid == null || grid.length == 0 || grid[0].length == 0) {
  12.             return 0;
  13.         }
  14.         int rows = grid.length, columns = grid[0].length;
  15.         int[][] dp = new int[rows][columns];
  16.         dp[0][0] = grid[0][0];
  17.         for (int i = 1; i < rows; i++) {
  18.             dp[i][0] = dp[i - 1][0] + grid[i][0];
  19.         }
  20.         for (int j = 1; j < columns; j++) {
  21.             dp[0][j] = dp[0][j - 1] + grid[0][j];
  22.         }
  23.         for (int i = 1; i < rows; i++) {
  24.             for (int j = 1; j < columns; j++) {
  25.                 dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
  26.             }
  27.         }
  28.         return dp[rows - 1][columns - 1];
  29.     }
  31. }