Python AC with 123ms,7 lines


  • 0
    S
    class Solution:
        # @param grid, a list of lists of integers
        # @return an integer
        def minPathSum(self, grid):
            m, n = len(grid), len(grid[0])
            for i in range(1,m): grid[i][0] += grid[i-1][0]
            for i in range(1,n): grid[0][i] += grid[0][i-1]
            for i in range(1,m):
                for j in range(1,n):
                    grid[i][j] += min(grid[i][j-1], grid[i-1][j])
            return grid[m - 1][n - 1]

  • 0
    S

    If search from both sides,may reduce the time to O(mn/2) ?


Log in to reply
 

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