class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m, n = len(grid), len(grid[0])
        sums = grid
        for i in range(1, m):
            sums[i][0] = sums[i - 1][0] + grid[i][0]
        for j in range(1, n):
            sums[0][j] = sums[0][j - 1] + grid[0][j]
        for i in range(1, m):
            for j in range(1, n):
                sums[i][j] = min(sums[i - 1][j], sums[i][j - 1]) + grid[i][j]
        print_Matrix(sums)
        return sums[-1][-1]

    def minPathSum2(self, grid):
        m, n = len(grid), len(grid[0])
        cur = [grid[0][0]] * m
        for i in range(1, m):
            cur[i] = cur[i - 1] + grid[i][0]
        for j in range(1, n):
            cur[0] += grid[0][j]
            for i in range(1, m):
                cur[i] = min(cur[i - 1], cur[i]) + grid[i][j]
        print(cur)
        return cur[-1]

    def minPathSum3(self, grid):
        cur = [0] + [1e10] * (len(grid[0]) - 1)
        for row in grid:
            for i in range(len(grid[0])):
                cur[i] = row[i] + min(cur[i - 1] if i > 0 else cur[i], cur[i])
        return cur[-1]



def print_Matrix(matrix):
    for row in matrix:
        print(row)
    print()

def main():
    grid = [[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]
    print_Matrix(grid)
    test = Solution()
    #print(test.minPathSum(grid))
    print(test.minPathSum2(grid))
    print(test.minPathSum3(grid))

main()
