[LeetCode]动态规划，一招团灭最小路径问题

2023-12-19 14:32
文章标签 leetcode 动态 规划 问题 路径 最小 一招 团灭

本文主要是介绍[LeetCode]动态规划，一招团灭最小路径问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

动态规划是求解“最小路径”的常用方法之一，LeetCode上关于“最小路径”的题目如下：

  • 64.最小路径和：https://leetcode-cn.com/problems/minimum-path-sum/
  • 120.三角形最小路径和：https://leetcode-cn.com/problems/triangle/
  • 931.下降路径最小和：https://leetcode-cn.com/problems/minimum-falling-path-sum/
  • 1289.下降路径最小和Ⅱ：https://leetcode-cn.com/problems/minimum-falling-path-sum-ii/

关于动态规划，可以访问Jungle之前的博客：

  • [LeetCode]动态规划及LeetCode题解分析
  • [LeetCode]动态规划LeetCode[简单]题全解
  • [LeetCode]动态规划之打家劫舍ⅠⅡⅢ
  • [LeetCode]动态规划，一举歼灭“股票买卖的最佳时机“问题！

本文，Jungle将采用动态规划，一举解决上述问题。

1.思路分析

我们以64.最小路径和为例，分析采用动态规划求解该类问题的基本思路。题目描述如下：

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

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

示例:

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

 在之前的文章我们已经提到过，使用动态规划求解问题的三大步骤，这里我们也将遵循这三大步骤：

（1）明确数组元素代表的含义

题目中是给定二维地图，我们使用二维数组dp[][]。那么对于数组元素dp[i][j]代表什么呢？——机器人走到网格(i,j)时的最小路径值。

（2）寻找递推关系，务必考虑特殊情况下的递推关系

题目中明确告诉“机器人每次只能向下或者向右移动一步”，因此，机器人走到(i,j)，有可能是从(i-1,j)向下走，也可能是从(i,j-1)向右走一步。到底该走哪一步呢？因为要求路径和最小，所以取决于dp[i-1][j]和dp[i][j-1]的大小。也就是说，dp[i][j]=grid[i][j]+min(dp[i-1][j]+dp[i][j-1]).

这里有没有特殊情况呢？显然有的，那就是机器人位于网格边界时（网格上面第一横排和左边第一竖排），上述递推关系需要修改：

  • 当机器人位于网格第一横排时，i=0，dp[0][j]只能从dp[0][j-1]向右移动一步得到，即dp[0][j] = grid[0][j]+dp[0][j-1]；
  • 当机器人位于网格第一竖排时，j=0，dp[i][0]只能从dp[i-1][0]向下移动一步得到，即dp[i][0] =grid[i-1][0]+dp[i-1][0]；

（3）数组初始化

机器人最初位于网格左上角，dp[0][0]是唯一开始点，所以dp[0][0] = grid[0][0].

（4）代码

本题不必重新声明二维数组dp，可以直接利用原有二维数组。

int minPathSum(vector<vector<int>>& grid) {int i = 0, j = 0;for (i = 0; i<grid.size(); i++){for (j = 0; j<grid[0].size(); j++){if (i == 0 && j == 0){continue;}else if (i == 0){grid[i][j] += grid[i][j - 1];}else if (j == 0){grid[i][j] += grid[i - 1][j];}else{grid[i][j] = grid[i][j] + (grid[i][j - 1]<grid[i - 1][j] ? grid[i][j - 1] : grid[i - 1][j]);}}}return grid[grid.size() - 1][grid[0].size() - 1];
}

2.LeetCode题解

64. 最小路径和

见上述分析示例。

120. 三角形最小路径和

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

这题把矩形换成了三角形。有什么区别？总体上思路是一样的，区别在于边界条件。

（1）明确数组元素代表的含义

dp[i][j]——走到网格(i,j)时的最小路径值。

（2）寻找递推关系，务必考虑特殊情况下的递推关系

题目中要求“每一步只能移动到下一行中相邻的结点上”，因此，走到(i,j)，有可能是从(i-1,j-1)向下走，也可能是从(i-1,j)向下走。到底该走哪一步呢？因为要求路径和最小，所以取决于dp[i-1][j]和dp[i][j-1]的大小。也就是说，dp[i][j]=triangle[i][j]+min(dp[i-1][j]+dp[i-1][j]).

这里同样有特殊情况——位于网格边界时。比上一题更加复杂的是，这道题有三角形顶点和三角形两腰上三个边界条件需要考虑，上述递推关系需要修改：

  • 当位于三角形左腰上时，即j=0，dp[i][0]只能从dp[i-1][0]向下移动一步得到，即dp[i][j] = triangle[i][j] + dp[i - 1][j]；
  • 当位于三角形右腰上时，即i=j，dp[i][j]只能从dp[i-1][j-1]向下移动一步得到，即dp[i][j] = triangle[i][j] + dp[i - 1][j - 1]；

同时，因为这一题目是要求走到底部，而不是固定走到最右下角的位置。所以定义变量min保存最小值。

（3）数组初始化

最初位于三角形顶点，dp[0][0]是唯一开始点，所以dp[0][0] = triangle[0][0].

（4）代码

int minimumTotal(vector<vector<int>>& triangle) {int col = triangle.size();if (col == 0){return 0;}if (col == 1){return triangle[0][0];}int **dp = new int*[col];for (int i = 0; i<col; i++){dp[i] = new int[i + 1];}dp[0][0] = triangle[0][0];int min = 0;for (int i = 1; i<col; i++){for (int j = 0; j<triangle[i].size(); j++){if (j == 0){dp[i][j] = triangle[i][j] + dp[i - 1][j];min = dp[i][j];}else if (j == i){dp[i][j] = triangle[i][j] + dp[i - 1][j - 1];}else{dp[i][j] = triangle[i][j] + (dp[i - 1][j - 1] < dp[i - 1][j] ? dp[i - 1][j - 1] : dp[i - 1][j]);}if (dp[i][j]<min){min = dp[i][j];}}}return min;
}

931. 下降路径最小和

给定一个方形整数数组 A，我们想要得到通过 A 的下降路径的最小和。

下降路径可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列。

 

示例：

输入：[[1,2,3],[4,5,6],[7,8,9]]
输出：12
解释：
可能的下降路径有：
[1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9]
[2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,8], [2,6,9]
[3,5,7], [3,5,8], [3,5,9], [3,6,8], [3,6,9]
和最小的下降路径是 [1,4,7]，所以答案是 12。

提示：

1 <= A.length == A[0].length <= 100
-100 <= A[i][j] <= 100

（1）明确数组元素代表的含义

dp[i][j]——走到网格(i,j)时的最小路径和。

（2）寻找递推关系，务必考虑特殊情况下的递推关系

题目中要求“从每一行中选择一个元素”并且“在下一行选择的元素和当前行所选元素最多相隔一列”，因此，走到(i,j)，可能是从(i-1,j-1)、(i-1,j)或者(i-1,j+1)三个位置出发达到。到底该走哪一步呢？因为要求路径和最小，所以取决于dp[i-1][j-1]、dp[i-1][j]和dp[i-1][j+1]的大小，即dp[i][j] = A[i][j]+min(dp[i-1][j-1],min(dp[i-1][j],dp[i-1][j+1])).

特殊情况——位于网格边界时：

  • 当位于左边界时，即j=0，dp[i][0]只能从dp[i-1][j]或dp[i-1][j+1]出发达到，即dp[i][j] = A[i][j]+min(dp[i-1][j],dp[i-1][j+1])；
  • 当位于右边界时，即j=len-1，dp[i][j]只能从dp[i-1][j-1]或dp[i-1][j]出发达到，即dp[i][j] = A[i][j]+min(dp[i-1][j-1],dp[i-1][j])​​​​​​​；

同时，因为这一题目是要求走到底部，而不是固定走到最右下角的位置。所以定义变量Min保存最小值。

（3）数组初始化

题目要求，“下降路径可以从第一行中的任何元素开始”，所以dp[0][j] = A[0][j]

（4）代码

int minFallingPathSum(vector<vector<int>>& A) {int row = A.size();int col = A[0].size();if (row == 0 || col == 0){return 0;}if (row == 1){sort(A[0].begin(), A[0].end());return A[0][0];}vector<vector<int>>dp(row, vector<int>(col, 0));int Min = 0;for (int j = 0; j<col; j++){dp[0][j] = A[0][j];}for (int i = 1; i<row; i++){for (int j = 0; j<col; j++){if (j == 0){dp[i][j] = A[i][j] + min(dp[i - 1][j], dp[i - 1][j + 1]);}else if (j == col - 1){dp[i][j] = A[i][j] + min(dp[i - 1][j - 1], dp[i - 1][j]);}else{dp[i][j] = A[i][j] + min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i - 1][j + 1]));}if (i == row - 1){if (j == 0){Min = dp[i][0];}if (dp[i][j]<Min){Min = dp[i][j];}}}}return Min;
}

1289. 下降路径最小和 II

给你一个整数方阵 arr ，定义「非零偏移下降路径」为：从 arr 数组中的每一行选择一个数字，且按顺序选出来的数字中，相邻数字不在原数组的同一列。

请你返回非零偏移下降路径数字和的最小值。

 

示例 1：

输入：arr = [[1,2,3],[4,5,6],[7,8,9]]
输出：13
解释：
所有非零偏移下降路径包括：
[1,5,9], [1,5,7], [1,6,7], [1,6,8],
[2,4,8], [2,4,9], [2,6,7], [2,6,8],
[3,4,8], [3,4,9], [3,5,7], [3,5,9]
下降路径中数字和最小的是 [1,5,7] ，所以答案是 13 。
 

提示：

1 <= arr.length == arr[i].length <= 200
-99 <= arr[i][j] <= 99

这一题与上一题的区别在于，“按顺序选出来的数字中，相邻数字不在原数组的同一列”。这道题标记为“困难”，难吗？不难。

（1）明确数组元素代表的含义

dp[i][j]——走到网格(i,j)时的最小路径和。

（2）寻找递推关系，务必考虑特殊情况下的递推关系

题目中要求“从每一行中选择一个元素”并且“相邻数字不在原数组的同一列”，因此，走到(i,j)，是由除了(i-1,j)之外的其他网格出发达到。要求路径最小，因此需要找到在(i,j)上一步的最小路径值。所以，dp[i][j] = arr[i][j]+min_dp(dp,i-1,j)，其中min_dp是一个函数，返回第i-1行中的最小路径值，第三个参数代表当前的j，所以在查找第i-1行中的最小路径值时，要排除掉第j个位置的路径值。

同时，因为这一题目是要求走到底部，而不是固定走到最右下角的位置。所以定义变量res保存最小值。

（3）数组初始化

题目要求，“下降路径可以从第一行中的任何元素开始”，所以dp[0][j] = arr[0][j]

（4）代码

int min_dp(vector<vector<int>>& dp, int i, int not_j){int Min = 201;for (int jj = 0; jj<dp.size(); jj++){if (jj == not_j){continue;}if (dp[i][jj]<Min){Min = dp[i][jj];}}return Min;
}
int minFallingPathSum(vector<vector<int>>& arr) {int len = arr.size();if (len == 0){return 0;}if (len == 1){return arr[0][0];}vector<vector<int>>dp(len, vector<int>(len, 0));int res;for (int k = 0; k<len; k++){dp[0][k] = arr[0][k];}for (int i = 1; i<len; i++){for (int j = 0; j<len; j++){dp[i][j] = arr[i][j] + min_dp(dp, i - 1, j);if (i == len - 1){if (j == 0){res = dp[i][j];}else if (dp[i][j]<res){res = dp[i][j];}}}}return res;
}

欢迎在评论区交流！

原创不易，谢谢点赞！ 

欢迎关注知乎专栏：Jungle是一个用Qt的工业Robot

欢迎关注Jungle的微信公众号：Jungle笔记

 

这篇关于[LeetCode]动态规划，一招团灭最小路径问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/512552。

相关文章

MySQL主从同步延迟问题的全面解决方案

MySQL主从同步延迟问题的全面解决方案

《MySQL主从同步延迟问题的全面解决方案》MySQL主从同步延迟是分布式数据库系统中的常见问题,会导致从库读取到过期数据,影响业务一致性,下面我将深入分析延迟原因并提供多层次的解决方案,需要的朋友可... 目录一、同步延迟原因深度分析1.1 主从复制原理回顾1.2 延迟产生的关键环节二、实时监控与诊断方案
阅读更多...
SQLyog中DELIMITER执行存储过程时出现前置缩进问题的解决方法

SQLyog中DELIMITER执行存储过程时出现前置缩进问题的解决方法

《SQLyog中DELIMITER执行存储过程时出现前置缩进问题的解决方法》在SQLyog中执行存储过程时出现的前置缩进问题,实际上反映了SQLyog对SQL语句解析的一个特殊行为,本文给大家介绍了详... 目录问题根源正确写法示例永久解决方案为什么命令行不受影响？最佳实践建议问题根源SQLyog的语句分
阅读更多...
慢sql提前分析预警和动态sql替换-Mybatis-SQL

慢sql提前分析预警和动态sql替换-Mybatis-SQL

《慢sql提前分析预警和动态sql替换-Mybatis-SQL》为防止慢SQL问题而开发的MyBatis组件,该组件能够在开发、测试阶段自动分析SQL语句,并在出现慢SQL问题时通过Ducc配置实现动... 目录背景解决思路开源方案调研设计方案详细设计使用方法1、引入依赖jar包2、配置组件XML3、核心配
阅读更多...
解决IDEA报错:编码GBK的不可映射字符问题

解决IDEA报错:编码GBK的不可映射字符问题

《解决IDEA报错:编码GBK的不可映射字符问题》：本文主要介绍解决IDEA报错:编码GBK的不可映射字符问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录IDEA报错:编码GBK的不可映射字符终端软件问题描述原因分析解决方案方法1：将命令改为方法2：右下jav
阅读更多...
MyBatis模糊查询报错：ParserException: not supported.pos 问题解决

MyBatis模糊查询报错：ParserException: not supported.pos 问题解决

《MyBatis模糊查询报错：ParserException:notsupported.pos问题解决》本文主要介绍了MyBatis模糊查询报错：ParserException:notsuppo... 目录问题描述问题根源错误SQL解析逻辑深层原因分析三种解决方案方案一：使用CONCAT函数（推荐）方案二：
阅读更多...
Redis 热 key 和大 key 问题小结

Redis 热 key 和大 key 问题小结

《Redis热key和大key问题小结》：本文主要介绍Redis热key和大key问题小结,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录一、什么是 Redis 热 key？热 key（Hot Key）定义： 热 key 常见表现：热 key 的风险：二、
阅读更多...
springboot使用Scheduling实现动态增删启停定时任务教程

springboot使用Scheduling实现动态增删启停定时任务教程

《springboot使用Scheduling实现动态增删启停定时任务教程》：本文主要介绍springboot使用Scheduling实现动态增删启停定时任务教程,具有很好的参考价值,希望对大家有... 目录1、配置定时任务需要的线程池2、创建ScheduledFuture的包装类3、注册定时任务，增加、删
阅读更多...
IntelliJ IDEA 中配置 Spring MVC 环境的详细步骤及问题解决

IntelliJ IDEA 中配置 Spring MVC 环境的详细步骤及问题解决

《IntelliJIDEA中配置SpringMVC环境的详细步骤及问题解决》：本文主要介绍IntelliJIDEA中配置SpringMVC环境的详细步骤及问题解决,本文分步骤结合实例给大... 目录步骤 1：创建 Maven Web 项目步骤 2：添加 Spring MVC 依赖1、保存后执行2、将新的依赖
阅读更多...
使用Python实现矢量路径的压缩、解压与可视化

使用Python实现矢量路径的压缩、解压与可视化

《使用Python实现矢量路径的压缩、解压与可视化》在图形设计和Web开发中,矢量路径数据的高效存储与传输至关重要,本文将通过一个Python示例,展示如何将复杂的矢量路径命令序列压缩为JSON格式,... 目录引言核心功能概述1. 路径命令解析2. 路径数据压缩3. 路径数据解压4. 可视化代码实现详解1
阅读更多...
Spring 中的循环引用问题解决方法

Spring 中的循环引用问题解决方法

《Spring中的循环引用问题解决方法》：本文主要介绍Spring中的循环引用问题解决方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录什么是循环引用？循环依赖三级缓存解决循环依赖二级缓存三级缓存本章来聊聊Spring 中的循环引用问题该如何解决。这里聊
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2