leetcode 64. Minimum Path Sum-最小

本题属于最小路径问题的简化版原题地址

初入门算法的同学见到这题可能会有些懵，首先会想到遍历去寻找每一个点的最优路径，这个思路是没有问题的但是如何实现的？

和本类问题相似的还有背包客问题、网络流优化等问题，这类问题有一种典型的解法就是采用动态规划算法，动态规划算法的典型应用求解以时间划分阶段的动态过程的优化问题。

那么看看本题的描述：

给定一个包含非负整数的 m*n网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入:[ [1,3,1], 1,5,1], [4,2,1]]输出:7解释:因为路径 1→3→1→1→1 的总和最小。

本题思路：

动态规划的特点要求利用到上一次的结果，是一种特殊的迭代思想，动态规划的关键是要得到递推关系式。对于本题，从原点到达（i, j）的最小路径等于 ：原点到达（i-1, j）最小路径与到达（i, j-1）最小路径中的最小值，即 dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]。而且本题可以不申请额外空间，直接在grid中修改参数即可，这使得空间复杂度得到了有效的利用，这类做法在实际场景中常常被用到。

具体的过程以及解释请详参代码。

class Solution:
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        n = len(grid)
        m = len(grid[0])
        for i in range(1,n):
            grid[i][0] = grid[i-1][0] + grid[i][0]   #首先需要寻找左边界各点的路径总和
    
        for j in range(1,m):
            grid[0][j] = grid[0][j-1] + grid[0][j]  #寻找上边界各点的路径总和
 
        for i in range(1,n):
            for j in range(1,m):
                grid[i][j] = min(grid[i-1][j] , grid[i][j-1]) + grid[i][j]  #以边界处为依据一步步推出内部个点的路径总和

        return grid[n-1][m-1]