30-Day LeetCoding Challenge Day 18: Minimum Path Sum

看來LeetCode開始在拉高難度了。今天又是medium…究竟hard什麼時候會出現呢？讓我們看下去…

好不管，題目要我們找出從左上走到右下，沿路踩到的數字加起來，怎麼走才會最小。注意：每一步都只能往右或往下。

那就是無懸念的DP題囉！直接來列公式吧！對任一個點(i,j)來說，我的上一步不是上面(i-1,j)就是左邊(i-1,j)，於是，從最左上角走到這的最小總和，只有幾種情形：

1. 我自己就是起點：我自己
2. 我在最上行：左邊那個點的結果 + 我自己
3. 我在最左列：上面那個點的結果 + 我自己
4. 我在中間其他點：(左邊那個點 和 上面那個點 的結果，取小的) + 我自己

公式列完，我們就得解，小心邊界值就好：

public class Solution {
    public int minPathSum(int[][] grid) {

        int height = grid.length;
        if (height == 0) {
            return 0;
        }

        int width = grid[0].length;
        if (width == 0) {
            return 0;
        }

        int[][] dp = new int[height][width];


        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {

                if (i == 0 && j == 0) {
                    dp[i][j] = grid[i][j];
                } else if (i == 0) {
                    dp[i][j] = dp[i][j - 1] + grid[i][j];
                } else if (j == 0) {
                    dp[i][j] = dp[i - 1][j] + grid[i][j];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
                }
            }
        }

        return dp[height - 1][width - 1];
    }
}

Happy Coding！