Concise DP Java Solution O(1) space


  • 0
    S

    Using original matrix could achieve O(1) space.

      public class Solution {
            public int minPathSum(int[][] grid) {
                // DP
                if(grid.length==0){return 0;}
                // base case
                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];
                // iteration
                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.