leetcode第64题，动态规划，要求在一个二维数组中，找出一条从左上到右下的路径，使得加起来的和最小。要求只能向下或者向右移动。
题目给了诸多限制，给了我们很好的处理办法。对于这种地图寻路，很明显DP是很好的思路。设立一个二维数组，大小和给定的二维数组相同，用来记录每个节点处最短路径的和。注意到，第一行和第一列的和是固定的，因为只能向下或者向右，所以可以先算出来。然后中间部分的最短路径和都有两种可能，一种是来自于上方的路径加和，还有的是来自于左方的路径加和，此时就要比较一下哪一个小，记录到对应位置即可，这样每个节点出发都是所有路径到这个节点最小的加和。最后只要输出末尾的加和项就可以了。
另外，python中二维数组很难开，搞不好会有副本复制的问题，因此这里我用了一种最保险的办法：d = [[0 for i in range(n)] for i in range(m)]
class Solution(object): def minPathSum(self, grid): """ :type grid: List[List[int]] :rtype: int """ m = len(grid) n = len(grid[0]) d = [[0 for i in range(n)] for i in range(m)] print d d[0][0] = grid[0][0] for i in range(1, n): d[0][i] = d[0][i-1]+grid[0][i] for i in range(1, m): d[i][0] = d[i-1][0]+grid[i][0] for i in range(1,m): for j in range(1,n): d[i][j] = min(d[i-1][j]+grid[i][j], d[i][j-1]+grid[i][j]) print d return d[-1][-1]