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:

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

    题意

    在矩形中找到一条路径，起点为左上顶点，终点为右下顶点，路径中只能向右或向下走，要求计算不同路径上数字之和的最小值。

    思路

    与 62. Unique Paths 和 63. Unique Paths Ⅱ 方法一致，但dp数组的含义不同：dp[i][j]表示到达(i, j)的多条路径中的最小数字和。

    代码实现 - 动态规划

    1. class Solution {
    2.     public int minPathSum(int[][] grid) {
    3.         int n = grid.length, m = grid[0].length;
    4.         int dp[][] = new int[n][m];
    6.         for (int i = 0; i < n; i++) {
    7.             for (int j = 0; j < m; j++) {
    8.                 // 第一行和第一列单独处理
    9.                 if (i == 0) {
    10.                     dp[i][j] = j == 0 ? grid[0][0] :grid[i][j] +dp[i][j - 1];
    11.                 } else if (j == 0) {
    12.                     dp[i][j] = grid[i][j] + dp[i - 1][j];
    13.                 } else {
    14.                     dp[i][j] = Math.min(grid[i][j] + dp[i][j - 1], grid[i][j] + dp[i - 1][j]);
    15.                 }
    16.             }
    17.         }
    19.         return dp[n-1][m - 1];
    20.     }
    21. }

    代码实现 - 滚动数组优化

    1. class Solution {
    2.     public int minPathSum(int[][] grid) {
    3.         int n = grid.length, m = grid[0].length;
    4.         int dp[] = new int[m];
    6.         for (int i = 0; i < n; i++) {
    7.             for (int j = 0; j < m; j++) {
    8.                 // 第一行和第一列单独处理
    9.                 if (i == 0) {
    10.                     dp[j] = j == 0 ? grid[0][0] : grid[i][j] + dp[j - 1];
    11.                 } else if (j == 0) {
    12.                     dp[j] = grid[i][j] + dp[j];
    13.                 } else {
    14.                     dp[j] = Math.min(grid[i][j] + dp[j - 1], grid[i][j] + dp[j]);
    15.                 }
    16.             }
    17.         }
    19.         return dp[m - 1];
    20.     }
    21. }