求解矩阵最短路径问题

互联网技术 waitig 558℃ 百度已收录 0评论

最近刷LeetCode,题目是这样的:
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example 1:

[[1,3,1],
[1,5,1],
[4,2,1]]
Given the above grid map, return 7. Because the path 1→3→1→1→1 minimizes the sum.

简单来说就是从[0][0]寻找出到[n-1][n-1]和最小的点。这里当然可以用暴力搜索去解决,不过用动态规划会更加简单。首先,分析这个问题,你需要寻找的其实就是从哪个位置到达所需要的点G[i][j]是最小的,这里建立一个新的矩阵,用来存储到达每个点的和,记为s[i][j],到达G[i][j],只有两个位置,即s[i-1][j]和s[i][j-1],那么利用动态规划我们就可以求出:
s[i][j]=min(s[i-1][j],s[i][j-1])+G[i][j]。基本思想解决了,剩下就是写代码了,这里用python实现:

class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        rows=len(grid)
        cols=len(grid[0])
        s=[[grid[0][0] for i in range(cols)] for i in range(rows)]#定义一个矩阵,与grid维数相同
        for i in range(1,cols):
            s[0][i]=s[0][i-1]+grid[0][i]#初始化第一列
        for i in range(1,rows):
            s[i][0]=s[i-1][0]+s[i][0]#初始化第一行
        for i in range(1,rows):
            for j in range(1,cols):
                s[i][j]=min(s[i][j-1],s[i-1][j])+grid[i][j]
        return s[rows-1][cols-1]

本文由【waitig】发表在等英博客
本文固定链接:求解矩阵最短路径问题
欢迎关注本站官方公众号,每日都有干货分享!
等英博客官方公众号
点赞 (0)分享 (0)