Simple python dp 70ms


  • 18
    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.


  • 0
    Z

    Can anyone tell me why the code below is wrong? maybe I shouldn't assign value to ans itself?
    Thank you!

    """
    def minPathSum(grid):
    if len(grid)==0:
    return 0
    m, n=len(grid), len(grid[0])
    ans= [[0 for _ in range(n+1)] for _ in range(m+1)]
    for i in range(1, m+1):
    for j in range(1, n+1):
    ans[i][j] += min(ans[i-1][j], ans[i][j-1]) + grid[i-1][j-1]

    return ans[m][n]
    """


Log in to reply
 

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