Ref: link

64. Minimum Path Sum (Medium)

We can only move either down or right at any point in time, so the minimum sum path to current position must come from top or left. Dp formula is dp[i][j] = Math.min(dp[i-1][j]+grid[i][j],dp[i][j-1]+grid[i][j]).

Time complexity is O(n^2). Space complexity is O(1). Here is the link.

public int minPathSum(int[][] grid) {
    for(int i =0;i<grid.length;i++){
        for(int j =0;j<grid[i].length;j++){
            int top = i==0?Integer.MAX_VALUE:grid[i-1][j]+grid[i][j];
            int left = j==0?Integer.MAX_VALUE:grid[i][j-1]+grid[i][j];
            grid[i][j] = i==0&&j==0?grid[i][j]:Math.min(top,left);
        }
    }
    return grid[grid.length-1][grid[0].length-1];
}

62. Unique Paths (Medium)

This problem is a little bit different from the previous problem. In the previous problem, we want the minimum sum path. In this problem, we need the number of all possible paths. There are only two ways to current position: from top or left. We need to sum these two ways. Therefore, dp formula is dp[i][j] = dp[i-1][j] + d[i][j-1].

Time complexity is O(mn). Space complexity is O(mn). Here is the link.

public int uniquePaths(int m, int n) {
    int[][]grid = new int[m][n];
    for(int i =0;i<m;i++){
        for(int j =0;j<n;j++){
            int top = i==0?0:grid[i-1][j];
            int left = j==0?0:grid[i][j-1];
            grid[i][j] = i==0&&j==0?1:top+left;
        }
    }
    return grid[m-1][n-1];
}