Minimum path sum

一次做對！好感動

。題目假設

給一個 m*n 矩陣，元素不為負數，求出和為最短的路徑，只能往右或往下

。重要問題

要怎樣在矩陣內行走，邊界條件

。直覺

要設定 cost

。解決方法可行性

一開始是想每次都往最小的走，但一定不行啊，因為當前比較小不代表後面也比較小

後來轉而想，對於每個元素，他有可能被選為路徑可能是從左邊或上面來

只要紀錄從 min(左邊, 上面) ，那就等於記住這條路的最小 cost，那把矩陣掃過後，f[m-1][n-1] 最右下元素就是最小路徑

。解決方案

。資料結構

二維陣列

。複雜度

O(n^2)

。遇到的困難點、想錯的地方

邊界條件要注意

public int minPathSum(int[][] grid) {
    if (grid == null || grid.length == 0) {
        return Integer.MAX_VALUE;
    }

    int m = grid.length;
    int n = grid[0].length;
    int f[][] = new int[m][n];
    f[0][0] = grid[0][0];

    for (int i=0; i<m; i++) {
        for (int j=0; j<n; j++) {
            //possible from left and not from top
            if (j-1 >= 0 && i == 0) {
                f[i][j] = grid[i][j] + f[i][j-1];
            }
            //possible from left and from top
            if (j-1 >= 0 && i != 0) {
                f[i][j] = grid[i][j] + Math.min(f[i][j-1], f[i-1][j]);
            }
            //possible from top not from left
            if (i-1 >= 0 && j == 0) {
               f[i][j] = grid[i][j] + f[i-1][j]; 
            }
        }
    }
    return f[m-1][n-1];
}