Simple python dp 70ms


  • 17
    L
    def minPathSum(self, grid):
        m = len(grid)
        n = len(grid[0])
        for i in range(1, n):
            grid[0][i] += grid[0][i-1]
        for i in range(1, m):
            grid[i][0] += grid[i-1][0]
        for i in range(1, m):
            for j in range(1, n):
                grid[i][j] += min(grid[i-1][j], grid[i][j-1])
        return grid[-1][-1]

  • 2
    T
    def minPathSum(self, grid):
            M, N = len(grid), len(grid[0]) 
            dp = [0] + [sys.maxint] * (N-1)
            for i in range(M):
                dp[0] = dp[0] + grid[i][0]
                for j in range(1, N):
                    dp[j] = min(dp[j-1], dp[j]) + grid[i][j]
            return dp[-1]

  • 0
    R

    Golang version:

    func minPathSum(grid [][]int) int {
        m := len(grid)
            n := len(grid[0])
            for  i := 0; i < m; i++ {
                for  j := 0; j < n; j++ {
                    if i == 0 && j != 0 {
                        grid[i][j] += grid[i][j-1]
                    } else if i != 0 && j == 0 {
                        grid[i][j] += grid[i-1][j]
                    } else if i == 0 && j == 0 {
                        grid[i][j] = grid[i][j]
                    } else {
                        grid[i][j] += min(grid[i][j-1], grid[i-1][j]);
                    }
                }
            }
            return grid[m-1][n-1]
    }
    
    func min(a int, b int) int {
        if a > b {
            return b
        } else {
            return a
        }
    }
    

    Javascript version:

    /**
     * @param {number[][]} grid
     * @return {number}
     */
    var minPathSum = function(grid) {
        var m = grid.length;
            var n = grid[0].length;
            for(var i = 0; i < m; i++) {
                for(var j = 0; j < n; j++) {
                    if(i == 0 && j != 0) {
                        grid[i][j] += grid[i][j-1];
                    } else if(i != 0 && j == 0) {
                        grid[i][j] += grid[i-1][j];
                    } else if(i == 0 && j == 0) {
                        grid[i][j] = grid[i][j];
                    } else {
                        grid[i][j] += Math.min(grid[i][j-1], grid[i-1][j]);
                    }
                }
            }
            return grid[m-1][n-1];
    };
    

  • 0
    L

    @luanmaova
    can not believe we have the exact same code, even with the variable name, the Indentation, everything lol.


Log in to reply
 

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