43.LeetCode64. 最小路径和

• 标签： 动态规划 数组
• 难度： 简单

---

• 题目描述

• 我的解法

按照从左到右，从上到下的顺序依次计算从 左上角 到 每个网格 的最近距离，方法是： 对每个网格，比较左邻域的网格 距离值（注意，这个值是已经计算得到最近距离值，而非原先的网格数字值）和上邻域的网格 距离值，取较小者加上自身 数字值，作为从左上角到该网格的 距离值， 下图解释了上述递推过程。

import numpy as np
class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m = len(grid)
        n = len(grid[0])
        result = np.zeros((m+1, n+1))
        result[0,:] = float('inf')
        result[:,0] = float('inf')
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if(i==1 and j ==1):
                    result[i][j] = grid[i-1][j-1]
                else:    
                    neighbor = min(result[i-1][j], result[i][j-1])
                    result[i][j] = neighbor + grid[i-1][j-1]
                
        return int(result[m][n])

• 其他解法

暂略。