Matrix DP - 64. Minimum Path Sum

https://leetcode.com/problems/minimum-path-sum/description/

这个题目写了三遍，才写出正确的Solution。前两个错误，都是因为初始化错误。

class Solution {
    public int minPathSum(int[][] grid) {
        int rowNum = grid.length;
        int colNum = grid[0].length;
        int[][] dp = new int[rowNum][colNum];
        
        // initialization
        dp[0][0] = grid[0][0];
        for (int i = 1; i < rowNum; i++) {
            dp[i][0] = grid[i][0] + dp[i - 1][0];
        }
        for (int j = 1; j < colNum; j++) {
            dp[0][j] = grid[0][j] + dp[0][j - 1];
        }
        
        for (int i = 1; i < rowNum; i++) {
            for (int j = 1; j < colNum; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        
        return dp[rowNum - 1][colNum - 1];
    }
    
    public int minPathSumWrong2(int[][] grid) {
        int rowNum = grid.length;
        int colNum = grid[0].length;
        int[][] dp = new int[rowNum][colNum];
        
        for (int i = 0; i < rowNum; i++) {
            dp[i][0] = grid[i][0];  // wrong!!!
        }
        for (int j = 0; j < colNum; j++) {
            dp[0][j] = grid[0][j];  // wrong!!!
        }
        ...
    }
    
    public int minPathSumWrong(int[][] grid) {
        int rowNum = grid.length;
        int colNum = grid[0].length;
        int[][] dp = new int[rowNum + 1][colNum + 1];

        // wrong: 试图将 dp 首行首列初始化为 0，实际上是不对的

        for (int i = 0; i < rowNum; i++) {
            for (int j = 0; j < colNum; j++) {
                dp[i + 1][j + 1] = Math.min(dp[i][j + 1], dp[i + 1][j]) + grid[i][j];
            }
        }
        /**
        Your input:
                [1,3,1],
                [1,5,1],
                [4,2,1]        
        Your stdout
          0, 0, 0, 0, 
          0, 1, 3, 1, 
          0, 1, 6, 2, 
          0, 4, 6, 3, 
        */
        return dp[rowNum][colNum];
    }
}