DP Solution, Linear space


  • 28
    L

    You can only reach a cell by going from its left or top neighbor.

    class Solution {
    public:
        int minPathSum(vector<vector<int> > &grid) {
            if(!grid.size())return 0;
            const int rows=grid.size(),cols=grid[0].size();
            // r[i] == min path sum to previous row's column i.
            vector<int> r(cols,0);
            int i,j;
            r[0]=grid[0][0];
            for(j=1;j<cols;j++){
                r[j]=grid[0][j]+r[j-1];       
            }
            for(i=1;i<rows;i++){
                r[0]+=grid[i][0];
                for(j=1;j<cols;j++){
                    r[j]=min(r[j-1],r[j])+grid[i][j];
                }
            }
            return r[cols-1];
        }
    };

  • 0
    C

    Python version:

    def minPathSum(self, grid):
        if not grid:
            return None
        m, n = len(grid), len(grid[0])
        table = [[float('inf')] * (n + 1) for _ in range(m + 1)]
        table[0][1] = 0
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                table[i][j] = min(table[i - 1][j], table[i][j - 1]) + grid[i - 1][j - 1]
        return table[-1][-1]

  • 0
    W

    Yeah, saving much space.


  • 0
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        int[][] dp = new int[grid.length][grid[0].length];
    
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (i == 0 && j == 0) dp[i][j] = grid[i][j];
                else if (i == 0) dp[i][j] = grid[i][j] + dp[i][j - 1];
                else if (j == 0) dp[i][j] = grid[i][j] + dp[i - 1][j];
                else dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[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.