算法64. Minimum Path Sum

64. Minimum Path Sum
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example:

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

给一个 m * x 的非负数矩阵，找到从左上到右下路径和最小的路径。
提示：
同一时间只能往右或者下走。

解：
这种题是典型的可以使用动态规划算法的题，跑到某一个点，比如 m * n，只能有两种走法：[m-1,n] 或者 [m, n-1]，那就哪个和少走哪个。

以下为代码：

public int minPathSum(int[][] grid) {
    // 构建一个存储路径和的矩阵，大小和参数一样
    int[][] paths = new int[grid.length][grid[0].length];
    return minPathSum(grid, 0, 0, paths);
}

private int minPathSum(int[][] grid, int row, int col, int[][] paths) {
    if (row == grid.length - 1 && col == grid[0].length - 1) {// 走到了右下角
        return grid[row][col];
    }
    if (paths[row][col] != 0) {
        return paths[row][col];
    }

    int rowInc = Integer.MAX_VALUE, colInc = Integer.MAX_VALUE;
    if (row < grid.length - 1) {
        rowInc = minPathSum(grid, row + 1, col, paths);
    }
    if (col < grid[0].length - 1) {
        colInc = minPathSum(grid, row, col + 1, paths);
    }
    paths[row][col] = Math.min(rowInc, colInc) + grid[row][col];
    return paths[row][col];
}