'''

64. Minimum Path Sum

Given a m x 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.

'''

class Solution(object):

# runtime 68ms

def minPathSum(self, grid):

"""

:type grid: List[List[int]]

:rtype: int

"""

if not grid:

return 0

if len(grid[0]) == 1 or len(grid) == 1:

return sum(grid)

m = len(grid)

n = len(grid[0])

minDP = [[0 for _ in range(n)] for _ in range(m)]

for line in grid:

print(line)

print("#################################")

minDP[0][0] = grid[0][0]

for i in range(m):

for j in range(n):

if i == 0 and j == 0:

continue

elif i == 0 and j != 0:

minDP[i][j] = minDP[i][j - 1] + grid[i][j]

elif j == 0 and i != 0:

minDP[i][j] = minDP[i - 1][j] + grid[i][j]

else:

minDP[i][j] = min(minDP[i - 1][j], minDP[i][j - 1]) + grid[i][j]

print(minDP[i])

return minDP[m - 1][n - 1]

def test():

grid = [[1, 2, 3], [2, 3, 4], [3, 4, 5]]

sol = Solution()

print(sol.minPathSum(grid))

if __name__ == "__main__":

test()