64. Minimum Path Sum
Given a m × n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note:
You can only move either down or right at any point in time.
Solution: DP
class Solution(object):
def minPathSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
rows = len(grid)
cols = len(grid[0])
sums = [float('inf')] * cols
sums[0] = 0
for row in xrange(0, rows):
sums[0] += grid[row][0]
for col in xrange(1, cols):
sums[col] = min(sums[col - 1], sums[col]) + grid[row][col]
return sums[-1]