Easy to understand O(mn) time and O(1) space DP solution in Java with explanation


  • 0
    Y

    Use the given 2D array and update grid[i][j] to store the minimum path until [i][j].
    First update the upper most row as the dynamic programming algorithm's initial value.
    Do the same to the left most column.
    Then update grid[i][j] with the minimum path reaching to, from i = 1, j = 1 from left to right (i++), up to down(j++).
    Then we will get the result at bottom right.
    The time complexity is O(mn) since we have a two levels loop
    The space complexity is O(1)

    public class Solution {
    public int minPathSum(int[][] grid) {
    // redefine grid[i][j] to the minimum path reaching grid[i][j]
    for (int i = 1; i < grid.length; ++i) {
    grid[i][0] += grid[i - 1][0];
    }
    for (int j = 1; j < grid[0].length; ++j) {
    grid[0][j] += grid[0][j - 1];
    }
    for (int i = 1; i < grid.length; ++i) {
    for (int j = 1; j < grid[0].length; ++j) {
    grid[i][j] += Math.min(grid[i -1][j], grid[i][j -1]);
    }
    }
    return grid[grid.length - 1][grid[0].length - 1];
    }
    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.