leetcode: 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.
#
# Note: You can only move either down or right at any point in time.
#
# Example 1:
# [[1,3,1],
#  [1,5,1],
#  [4,2,1]]
#
# Given the above grid map, return 7. Because the path 1→3→1→1→1 minimizes the sum.

class Solution():
    def minPathSum(self, x):
        m, n = len(x[0]), len(x)
        way = [0] * m
        way[0] = x[0][0]
        for j in range(1, m):
            way[j] = way[j-1] + x[0][j]
        for i in range(1, n):
            way[0] += x[i][0]
            for j in range(1, m):
                way[j] = min(way[j-1], way[j]) + x[i][j]
        return way[-1]


if __name__ == "__main__":
    assert Solution().minPathSum([[0,1], [1,0]]) == 1
    assert Solution().minPathSum([[1,3,1], [1,5,1], [4,2,1]]) == 7