Thinking process

how to get to the bottom-right?

the current minimum sum depends only on the state at the top and the state at the left

be careful with bound of boundary

Mistakes

should the seize of dp matrix be (n + 1) * (m + 1) or n * m?

• if it's the first, then it violates the condition that starting from top-left element.

Time Complexity

O(n*m)

public class Solution {
    //1 1 1
    //1 2 1
    //2 1 1
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return -1;

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

        int[][] memo = new int[n][m];

        //init
        for (int i = 0; i <= n - 1; ++i) {
            for (int j = 0; j <= m - 1; ++j) {
                memo[i][j] = Integer.MAX_VALUE;
            }
        }

        memo[0][0] = grid[0][0];

        //dp
        for (int i = 0; i <= n - 1; ++i) {
            for (int j = 0; j <= m - 1; ++j) {
                if (j - 1 >= 0) {
                    memo[i][j] = Math.min(memo[i][j], memo[i][j - 1] + grid[i][j]);//from left
                }

                if (i - 1 >= 0) {
                    memo[i][j] = Math.min(memo[i][j], memo[i - 1][j] + grid[i][j]);//from top
                }
            }
        }


        return memo[n - 1][m - 1];
    }
}