LC-0064 Medium LeetCode

64. Minimum Path Sum

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 66% Topics: Array, Dynamic Programming, Matrix

Reading material

Arrays & Hashing 12 min 1-D Dynamic Programming 16 min Math & Geometry 12 min

Reference solution (spoiler · python)

# Time:  O(m * n)
# Space: O(m + n)

class Solution(object):
    # @param grid, a list of lists of integers
    # @return an integer
    def minPathSum(self, grid):
        sum = list(grid[0])
        for j in xrange(1, len(grid[0])):
            sum[j] = sum[j - 1] + grid[0][j]

        for i in xrange(1, len(grid)):
            sum[0] += grid[i][0]
            for j in xrange(1, len(grid[0])):
                sum[j] = min(sum[j - 1], sum[j]) + grid[i][j]

        return sum[-1]

Solution from kamyu104/LeetCode-Solutions · MIT