(1条消息) m x n 网格中的最小路径和

在上一篇中,我们通过分析,顺利完成了“三角形最小路径和”的动态规划题解。在本节中,我们继续看一道相似题型,以求能完全掌握这种“路径和”的问题。话不多说,先看题目:

01、题目分析

第64题:最小路径和
给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

说明:每次只能向下或者向右移动一步。

示例:

输入:[  [1,3,1],  [1,5,1],  [4,2,1]]输出: 7解释: 因为路径 1→3→1→1→1 的总和最小。

这道题有一定难度哦!如果没有思路请回顾上一篇的学习内容!

不建议直接看题解!

02、题目图解

首先我们分析题目,要找的是 最小路径和, 这是个啥意思呢?假设我们有一个 m * n 的矩形 :[[1,3,1],[1,5,1],[4,2,1]]

那从左上角到右下角的最小路径和,我们可以很容易看出就是 1-3-1-1-1 ,这一条路径,结果等于 7 。

题目明确了,我们继续进行分析。该题与上一道求三角形最小路径和一样,题目明显符合可以从子问题的最优解进行构建,所以我们考虑使用动态规划进行求解。首先,我们定义状态:

dp[i][j] : 表示包含第i行j列元素的最小路径和

同样,因为任何一条到达右下角的路径,都会经过 [0,0] 这个元素。所以我们需要对 dp[0][0] 进行初始化。

dp[0][0] = [0][0]位置所在的元素值

继续分析,根据题目给的条件,如果我们要求 dp[i][j] ,那么它一定是从自己的上方或者左边移动而来。如下图所示:

5,只能从3或者1移动而来2,只能从5或者4移动而来4,从1移动而来3,从1移动而来 (红色位置必须从蓝色位置移动而来)

进而我们得到状态转移方程:

dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j]

同样我们需要考虑两种特殊情况:

  • 最上面一行,只能由左边移动而来(1-3-1)

  • 最左边一列,只能由上面移动而来(1-1-4)

最后,因为我们的目标是从左上角走到右下角整个网格的最小路径和其实就是包含右下角元素的最小路径和。即:

设:dp的长度为l 最终结果就是:dp[l-1][len(dp[l-1])-1]

综上我们就分析完了,我们总共进行了 4 步:

  1. 定义状态

  2. 总结状态转移方程

  3. 分析状态转移方程不能满足的特殊情况。

  4. 得到最终解

03、GO语言示例

根据以上分析,可以得到代码如下:

func minPathSum(grid [][]int) int {l := len(grid)if l < 1 {return 0}dp := make([][]int, l)for i, arr := range grid {dp[i] = make([]int, len(arr))}dp[0][0] = grid[0][0]for i := 0; i < l; i++ {for j := 0; j < len(grid[i]); j++ {if i == 0 && j != 0 {dp[i][j] = dp[i][j-1] + grid[i][j]} else if j == 0 && i != 0 {dp[i][j] = dp[i-1][j] + grid[i][j]} else if i !=0 && j != 0 {dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]}}}return dp[l-1][len(dp[l-1])-1]}func min(a, b int) int {if a > b {return b}return a}

运行结果:

同样,运行上面的代码,我们发现使用的内存过大。有没有什么办法可以压缩内存呢?通过观察我们发现,在我们自左上角到右下角计算各个节点的最小路径和的过程中,我们只需要使用到之前已经累积计算完毕的数据,并且不会再次访问之前的元素数据。绘制成图如下:(大家看这个过程像不像扫雷,其实如果大家研究扫雷外挂的话,就会发现在扫雷的核心算法中,就有一处颇为类似这种分析方法,这里就不深究了)

优化后的代码如下:

func minPathSum(grid [][]int) int {l := len(grid)if l < 1 {return 0}for i := 0; i < l; i++ {for j := 0; j < len(grid[i]); j++ {if i == 0 && j != 0 {grid[i][j] = grid[i][j-1] + grid[i][j]} else if j == 0 && i != 0 {grid[i][j] = grid[i-1][j] + grid[i][j]} else if i !=0 && j != 0 {grid[i][j] = min(grid[i-1][j], grid[i][j-1]) + grid[i][j]}}}return grid[l-1][len(grid[l-1])-1]}func min(a, b int) int {if a > b {return b}return a}

运行结果:

课后思考:路径和类问题和之前的子序列类问题有何区别?


我把我写的所有题解都整理成了一本电子书,每道题都配有完整图解。

(0)

相关推荐

  • Trapcode Particular 5 - Emitter

    Emitter(发射器)属性组是粒子诞生的地方,它具有形状.样式和位置等属性,并决定着发射粒子的速度及粒子自身的运动速率. Emitter Type 发射器类型 --Point 点 所有粒子从同一个位 ...

  • 干货:图解算法——动态规划系列

    动态规划系列一:爬楼梯 1.1 概念讲解 讲解动态规划的资料很多,官方的定义是指把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解.概念中的各阶段之间的关系,其实指的就是状态转移方程. ...

  • ​LeetCode刷题实战63:不同路径 II

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • 每日一题 C++版(走迷宫)

    编程是很多偏计算机.人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用.因此小白决定开辟一个新的板块"每日一题",通过每天一道编程题目来强化和锻炼自己的编程能力 ...

  • (59条消息) 终于讲清楚了nodejs中exports和module.exports的区别

    module.exports 对象是由模块系统创建的.在我们自己写模块的时候,需要在模块最后写好模块接口,声明这个模块对外暴露什么内容,module.exports 提供了暴露接口的方法. 1.返回一 ...

  • (1条消息) Android Studio在Gradle中调用cmd脚本

    Gradle中调用cmd 需要在Gradle编译时,调用某些脚本进行文件操作,比如:头文件更新,或者动态链接库文件的更新等,需要借助脚本文件,并且不需要手动运行,那么如何使用Gradle呢? 如下代码 ...

  • (3条消息) Linux(CentOS7)中安装JDK

    目录 1.下载Oralce JDK 2.卸载Open JDK 2.1.检查一下系统中的jdk版本 2.2.检测jdk安装包 2.3.卸载openjdk 3.上传下载好的Oralce JDK到Linux ...

  • (6条消息) mysql取出每个分组中最新的记录

    原文:深度分析mysql GROUP BY 与 ORDER BY.mysql取出每个分组中最新的记录.mysql 分组取最新的一条记录(整条记录) 1.建表.插入测试数据 CREATE TABLE ` ...

  • (5条消息) VC++学习之VC中常见问题

    (1)为什么某个类突然在工作区间里面突然看不见了? 只是类隐藏了,打开FILEVIEW,找到隐藏类的头文件,随便敲一下键盘的空格键,类就会在CLASSVIEW中显示了 (2)在基于对话框的程序中,一按 ...

  • (3条消息) 使用POI给word中的表格增加行

    需求:有一个给定的word文档,文档中有一个表格,该表格只有一个标题行.现在根据数据为表格增加行,并保留表格线条. 如下表格所示: 字段1 字段2 字段3 字段4 字段5 字段6 修改后的效果: 字段 ...

  • (36条消息) EasyWeChat在laravel框架中的使用技巧

    EasyWeChat在laravel框架中的使用技巧 laravel框架实战: EasyWeChat 文章目录 EasyWeChat公众号配置 报错:Failed to cache access to ...

  • (10条消息) Android:LinearLayout布局中Layout

    首先看一下LinearLayout布局中Layout_weight属性的作用:它是用来分配属于空间的一个属性,你可以设置他的权重.很多人不知道剩余空间是个什么概念,下面我先来说说剩余空间. 看下面代码 ...

  • (1条消息) MOS管在开关电路中的使用

    MOS管也就是常说的场效应管(FET),有结型场效应管.绝缘栅型场效应管(又分为增强型和耗尽型场效应管).也可以只分成两类P沟道和N沟道,这里我们就按照P沟道和N沟道分类.对MOS管分类不了解的可以自 ...