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:

Input:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

动态规划的4点要素：

• 状态 State 灵感，创造力，存储小规模问题的结果，很重要！！！
• 方程 Function 状态之间的联系，怎么通过小的状态，来算大的状态
• 初始化 Intialization 最极限的小状态是什么, 起点
• 答案 Answer 最大的那个状态是什么，终点

状态网格 State Grid：
dy[x][y] = d[x-1][y] or d[x][y-1] + grid[x][y]

class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        r = len(grid)
        c = len(grid[0])
        dy = grid
        # dy[x][y] = d[x-1][y] or d[x][y-1] + grid[x][y]
        for x in range(r):
            for y in range(c):
                if x == 0 and y==0:
                    continue
                    print('1')
                elif x==0:
                    dy[x][y] = dy[x][y-1] + grid[x][y]
                elif y==0:
                    dy[x][y] = dy[x-1][y] + grid[x][y]
                else:
                    a = dy[x][y-1] + grid[x][y]
                    b = dy[x-1][y] + grid[x][y]
                    dy[x][y] = b if a > b else a
        return dy[r-1][c-1]