编程开发 购物 网址 游戏 小说 歌词 快照 开发 股票 美女 新闻 笑话 | 汉字 软件 日历 阅读 下载 图书馆 编程 China
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
移动开发 架构设计 编程语言 互联网 开发经验 Web前端 开发总结
开发杂谈 系统运维 研发管理 数据库 云 计 算 Java开发
VC(MFC) Delphi VB C++(C语言) C++ Builder 其它开发语言 云计算 Java开发 .Net开发 IOS开发 Android开发 PHP语言 JavaScript
ASP语言 HTML(CSS) HTML5 Apache MSSQL数据库 Oracle数据库 PowerBuilder Informatica 其它数据库 硬件及嵌入式开发 Linux开发资料
  编程开发知识库 -> 互联网 -> 求解矩阵最短路径问题 -> 正文阅读
 

[互联网]求解矩阵最短路径问题[第1页]

最近刷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]

  互联网 最新文章
Stanford 英文词性标注(Part-of-speech)缩
基于窗口的实时统计
求解矩阵最短路径问题
SSL握手通信详解及linux下c/c++ SSL Socket
关于服务器上(Docker中)运行Java程序时区
python爬虫系列(六):强大的beautifulsou
[计算机网络笔记]第四部分——网络层 选路算
11.28 北京,念腾讯暑假,不思则惘吧!
web安全之
滑块验证码识别 java版本
上一篇文章      下一篇文章      查看所有文章
加:2017-10-29 21:57:41  更:2017-10-29 21:57:48 
VC(MFC) Delphi VB C++(C语言) C++ Builder 其它开发语言 云计算 Java开发 .Net开发 IOS开发 Android开发 PHP语言 JavaScript
ASP语言 HTML(CSS) HTML5 Apache MSSQL数据库 Oracle数据库 PowerBuilder Informatica 其它数据库 硬件及嵌入式开发 Linux开发资料
360图书馆 软件开发资料 文字转语音 购物精选 软件下载 新闻资讯 小游戏 Chinese Culture 股票 三丰软件 开发 中国文化 网文精选 阅读网 看图 日历 万年历 2018年10日历
2018-10-18 19:18:23
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  编程开发知识库