Paste_Image.png

My code:

public class Solution {
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0)
            return 0;
        
        if (grid.length == 1 && grid[0].length == 1)
            return grid[0][0];
        int row = grid.length;
        int col = grid[0].length;
        for (int i = 1; i < col; i++)
            grid[0][i] += grid[0][i - 1];
        for (int i = 1; i < row; i++)
            grid[i][0] += grid[i - 1][0];
        
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (grid[i][j - 1] < grid[i - 1][j])
                    grid[i][j] += grid[i][j - 1];
                else
                    grid[i][j] += grid[i - 1][j];
            }   
        }
        return grid[row - 1][col - 1];
    }
}

My test result:

![Upload Paste_Image.png failed. Please try again.]

這次題目不是很難，主要使用到了貪婪的思想前痘。
Greedy Algorithm.
從(1,1) 開始，我要保證每個格點的數值赂韵，是起點到這里的最近距離梆惯。
于是可以從(1,1) -> (1,col - 1)遍歷。
然后再從 (2, 1) -> (2, col - 1)遍歷宏娄。
然后不斷刷新最短距離毙石。如下圖示例廉沮。

![Upload Paste_Image.png failed. Please try again.]

**
總結：Array, Greedy Algorithm, DP
**

Anyway, Good luck, Richardo!

My code:

public class Solution {
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0)
            return -1;
        /** add row */
        for (int i = 1; i < grid[0].length; i++) 
            grid[0][i] += grid[0][i - 1];
        /** add col */
        for (int i = 1; i < grid.length; i++)
            grid[i][0] += grid[i - 1][0];
        /** deal with inner matrix */
        for (int i = 1; i < grid.length; i++) {
            for (int j = 1; j < grid[0].length; j++) {
                grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
            }
        }
        return grid[grid.length - 1][grid[0].length - 1];
    }
}

一遍過。也沒什么可說的徐矩。不難滞时。

Anyway, Good luck, Richardo!

差不多的思路。
Anyway, Good luck, Richardo! -- 08/07/2016