64. Minimum Path Sum

1. Question

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.

2. Examples

Example 1:

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

Example 2:

Input: grid = [[1,2,3],[4,5,6]]
Output: 12

3. Constraints

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 100

4. References

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/minimum-path-sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

5. Solutions

dp

class Solution {
    public int minPathSum(int[][] grid) {
        int[][] res = new int[grid.length][grid[0].length];
        for (int i = 0; i < res.length; i++) {
            for (int j = 0; j < res[0].length; j++) {
                if (i == 0 && j != 0) {
                    res[i][j] = res[i][j - 1] + grid[i][j];
                } else if (i != 0 && j == 0) {
                    res[i][j] = res[i - 1][j] + grid[i][j];
                } else if (i == 0 && j == 0) {
                    res[i][j] = grid[0][0];
                } else {
                    res[i][j] = 0;
                }
            }
        }

        for (int i = 1; i < res.length; i++) {
            for (int j = 1; j < res[0].length; j++) {
                if (res[i][j - 1] < res[i - 1][j]) {
                    res[i][j] = res[i][j - 1] + grid[i][j];
                } else {
                    res[i][j] = res[i - 1][j] + grid[i][j];
                }
            }
        }

        return res[grid.length - 1][grid[0].length - 1];

    }
}