矩阵的最小路径和

矩阵的最小路径和

读前福利，送大家一些电子书

64. 最小路径和

问题描述

给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。

示例：

输入：[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]

输出：12

分析问题

因为题目要求每次只能向右或者向下走，所以对于右下角的位置，只能通过两种方式到达，即

1. 右下角的上方位置向下走。
2. 右下角的左边位置向右走。

所以，对于最后一个状态来说，它只依赖于它上边的状态和它左边的状态，而与其它状态无关。因此，我们可以使用动态规划来求解，

其状态转移方程是 **dp[i] [j] = min(dp[i-1] [j] ，dp[i] [j-1])+matrix[i] [j] **。

下面我们来看一下临界条件，对于第一行的元素来说，它不能从它上边的状态转移过来，只能从左边的状态转移过来，所以第一行的状态转移方程为 dp[0] [j] = d[0] [j-1] + matrix[0] [j]。同理可知，对于第一列的元素来说，它不能从它左边的状态转移过来，只能从它的上边转移过来，所以第一列元素的状态转移方程为 dp[i] [0] = dp[i-1] [0] + matrix[i] [0]。

class Solution:
    def minPathSum(self , matrix ):
        # write code here
        m=len(matrix)
        if m==0:
            return 0
        n=len(matrix[0])

        #定义状态转移矩阵
        dp=[[0]*n for _ in range(m)]
        #第一个元素是matrix[0][0]
        dp[0][0]=matrix[0][0]

        #处理第一列元素
        for i in range(1,m):
            dp[i][0]=dp[i-1][0] + matrix[i][0]

        #处理第一行元素
        for j in range(1,n):
            dp[0][j]=dp[0][j-1] + matrix[0][j]

        for i in range(1,m):
            for j in range(1,n):
                dp[i][j]=min(dp[i-1][j],dp[i][j-1])+matrix[i][j]

        #最后一个元素就是最小路径和
        return dp[m-1][n-1]

该算法的时间复杂度和空间复杂度都是O(m*n)，其中m代表矩阵的行数，n代表矩阵的列数。

其实，我们也不需要重新申请一个空间dp，我们可以直接复用matrix即可。

class Solution:
    def minPathSum(self , matrix ):
        # write code here
        m=len(matrix)
        if m==0:
            return 0
        n=len(matrix[0])

        #处理第一列元素
        for i in range(1,m):
            matrix[i][0]=matrix[i-1][0] + matrix[i][0]

        #处理第一行元素
        for j in range(1,n):
            matrix[0][j]=matrix[0][j-1] + matrix[0][j]

        for i in range(1,m):
            for j in range(1,n):
                matrix[i][j]=min(matrix[i-1][j],matrix[i][j-1])+matrix[i][j]

        #最后一个元素就是最小路径和
        return matrix[m-1][n-1]