###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.

def minpathsum(grid):
  row = len(grid)
  col = len(grid[0])
  A = [[0 for _ in range(col)] for _ in range(row)]
  A[0][0] = grid[0][0]
  for i in range(1,col):
    A[0][i] = grid[0][i] + A[0][i-1]
  for i in range(1,row):
    A[i][0] = A[i-1][0] + grid[i][0]
  for i in range(1,row):
    for j in range(1,col):
      A[i][j] = min(grid[i-1,j],grid[i,j-1])+grid[i][j]
  return A[row-1][col-1]
 
#time O(m*n)
#space O(m+n)
class Solution:
    # @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]
    
if __name__ == "__main__":
    print Solution().minPathSum([[0,1]
                                ,[1,0]])
    print Solution().minPathSum([[1,3,1]
                                ,[1,5,1]
                                ,[4,2,1]])
