64. 最小路径和 现实路径

64. 最小路径和 现实路径.md

64. 最小路径和

给定一个包含非负整数的 *m* x *n* 网格 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

解题

原始数组
[1, 2, 3]
[2, 5, 6]
[1, 2, 7]
[4, 1, 6]
最小路径和路径： [1, 2, 1, 2, 1, 6]
sum = 13

public static void main(String[] args) {
    int[][] grid = {{1,2,3},
                    {2,5,6},
                    {1,2,7},
                    {4,1,6}};
    System.out.println("原始数组");
    for (int i = 0; i < grid.length; i++) {
        System.out.println(Arrays.toString(grid[i]));
    }
    int sum = minPathSum(grid);
    System.out.println("sum = " + sum);
}
public static int minPathSum(int[][] grid) {
    //动态规划
    int m = grid.length;
    int n = grid[0].length;
    int[][] dp = new int[m][n];
    dp[0][0]=grid[0][0];
    for (int i = 1; i < m; i++) {
        dp[i][0]=dp[i-1][0]+grid[i][0];
    }
    for (int i = 1;i < n; i++) {
        dp[0][i]=dp[0][i-1]+grid[0][i];
    }
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
        }
    }
  
    // 显示路径
    int r = m - 1;
    int c = n - 1;
    LinkedList<Integer> resultPath = new LinkedList<>();
    resultPath.add(grid[r][c]);
    while (true) {
        if (r - 1 >= 0 && c - 1 >= 0) {
            if (dp[r - 1][c] < dp[r][c - 1]) {
                resultPath.addFirst(grid[r - 1][c]);
                r = r - 1;
            } else {
                resultPath.addFirst(grid[r][c - 1]);
                c = c - 1;
            }
        } else if (r == 0 && c - 1 >= 0) {
            while (c - 1 >= 0) {
                resultPath.addFirst(grid[0][c - 1]);
                c = c - 1;
            }
        } else if (c == 0 && r - 1 >= 0) {
            while (r - 1 >= 0) {
                resultPath.addFirst(grid[r - 1][0]);
                r = r - 1;
            }
        } else {
            break;
        }
    }
    System.out.print("最小路径和路径： ");
    System.out.println(Arrays.toString(resultPath.toArray()));
    return dp[m-1][n-1];
}