LeetCode 64 in Python. Minimum Path Sum (最小路径和)

最小路径和有两种解法，解法一为不断判断每个位置的移动状态，即是向右移动还是向下移动，如此算法时间复杂度为O(mn)。解法二则利用动态规划的思想，从终点开始不断更新到达终点上一步的最小路径和，从而找到起点到终点的最小路径和，这种解法的时间复杂度为O(n)。本文给出解法二的代码实现。

示例：

图1 最小路径和示例 

代码：

class Solution:
    def minPathSum(self, grid):
        row, col = len(grid), len(grid[0])
        res = [[float("inf")] * (col + 1) for r in range(row + 1)]
        res[row][col - 1] = 0
        
        for r in range(row - 1, -1, -1):
            for c in range(col - 1, -1, -1):
                res[r][c] = grid[r][c] + min(res[r + 1][c], res[r][c + 1])
        return res[0][0]

解释：

图2 算法解释图  

1）res为一个储存当前位置最小路径和的二元数组，举例说明，如图2所示，res[2][2] = 1 + min(res[3][2], res[2][3])。为何要将res[row][col - 1] 设为0，原因在于在计算res[row - 1][col - 1]时res[row - 1][col - 1] = grid[row - 1][col - 1] + min(res[row][col - 1], res[row - 1][col]) ，要想使其=grid[row - 1][col - 1]， min(res[row][col - 1], res[row - 1][col])应该为0，故可设置res[row - 1][col]或res[row][col - 1]为0：

        for r in range(row - 1, -1, -1):

                for c in range(col - 1, -1, -1):

                        res[r][c] = grid[r][c] + min(res[r + 1][c], res[r][c + 1])

        注意：res数组规模为(row + 1) * (col + 1)，但数组下标从0开始，在遍历时需注意下标取值范围。

2）最终从起点到终点的最小路径和即储存在res[0][0]中。