一天一学: Leetcode - Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.

Code from http://www.darrensunny.me/leetcode-minimum-path-sum/

public int minPathSum(int[][] grid) {

        if (grid == null || grid.length == 0 || grid[0].length == 0)

            return 0;

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

        int[] dp = new int[n];

        // Find the minimum sum of all numbers along a path to grid[i][j]

        for (int i = 0; i < m; i++) {

            for (int j = 0; j < n; j++) {

                if (i == 0 && j == 0)   // The first cell

                    dp[j] = grid[i][j];

                else if (i == 0)        // Cells in the first row

                    dp[j] = dp[j-1] + grid[i][j];

                else if (j == 0)        // Cells in the first column

                    dp[j] += grid[i][j];

                else                    // Others

                    dp[j] = Math.min(dp[j-1], dp[j]) + grid[i][j];

            }

        }

 

        return dp[n-1];

    }

// DP, O(n^2) time, O(n^2) space

public int minPathSum(int[][] grid) {

        int row = grid.length;

        int col = grid[0].length;

         

        int[][] res = new int[row][col];

        // init

        res[0][0] = grid[0][0];

         

        // left

        for(int i = 1; i < row; i++) {

            res[i][0] = res[i - 1][0] + grid[i][0];

        }

        // top

        for(int j = 1; j < col; j++) {

            res[0][j] = res[0][j - 1] + grid[0][j];

        }

         

        // rest elements

        for(int i = 1; i < row; i++) {

            for(int j = 1; j < col; j++) {

                res[i][j] = grid[i][j] + Math.min(res[i - 1][j], res[i][j - 1]);

            }

        }

         

        return res[row - 1][col - 1];

    }

Code from http://joycelearning.blogspot.com/2013/10/leetcode-minimum-path-sum.html

public int minPathSum(int[][] grid) {

        int row = grid.length;

        int col = grid[0].length;

         

        int[] res = new int[col];

        // init

        Arrays.fill(res, Integer.MAX_VALUE);

        res[0] = 0;

         

        // rest elements

        for(int i = 0; i < row; i++) {

            // init the 0th sum = old 0th element + the new 0th element

            // just init the 0th column every time dynamically

            res[0] = res[0] + grid[i][0];

             

            // loop through each element of each row

            for(int j = 1; j < col; j++) {

                res[j] = grid[i][j] + Math.min(res[j], res[j - 1]);

            }

        }

         

        return res[col - 1];

    }

Read full article from 一天一学: Leetcode - Minimum Path Sum