网站标题有特殊符号,上海网站建设极简慕枫,住房和城乡建设部网站注册进度,小程序微信定制开发#x1f397;️ 主页#xff1a;小夜时雨 #x1f397;️专栏#xff1a;动态规划 #x1f397;️如何活着#xff0c;是我找寻的方向 目录 1. 题目解析2. 代码 1. 题目解析
题目链接: https://leetcode.cn/problems/minimum-path-sum/description/ 这道题目和之前一道… ️ 主页小夜时雨 ️专栏动态规划 ️如何活着是我找寻的方向 目录 1. 题目解析2. 代码 1. 题目解析
题目链接: https://leetcode.cn/problems/minimum-path-sum/description/ 这道题目和之前一道题 不同路径1力扣62: https://leetcode.cn/problems/unique-paths/description/ 有相似的地方, 建议先去看看那道题整理一下思路, 会简单一些.
通常动态规划的题目有五个大步骤进行解析, 接下来一一来进行分析.
1. 状态表示
动态规划的重点是状态表示, 我们通过状态表示才可以写出正确的状态转移方程, 状态表示我们通常都是根据 经验题目 要求来进行定义的. 比如本道题又是一个二维的矩阵, 那么依旧可以定义我们的状态表示为 dp[i][j]: 表示到达 (i, j) 这个位置时, 路径上的数字总和为最小 2. 状态转移方程
根据题目要求, 假如我们走到了 (i,j) 位置时, 我们可以从上面往下走或者是从左面往右走, 即是从 (i-1, j) 或者 (i, j-1) 往 (i, j) 的位置走。根据状态表示, dp[i][j] 的大小可以由两部分组成, 问的是路径总和为最小, 那么共有两条不同的路径: 从左往右走或者从上往下走求的应该是这二者中的最小值。从 (0, 0) 走到 (i-1, j) 的最小路径总和假设为 X , 那么从 (0, 0) 走到 (i, j) 的最小路径总和就是 X nums[i][j], 注意要加上 ij位置的数字。正好所对应的就是 dp[i - 1][j] 所表示的含义. 同理 dp[i][j - 1] 也是. 那么状态转移方程应如下表示: dp[i][j] Math.min(dp[i - 1][j]dp[i][j - 1]) nums[i][j] 但是有一个细节问题, 这里和不同路径1 不同的是 这里需要用到原数组我们通常也是采取多加一行一列的方式来避免出现 dp 表越界的情况 所以要注意映射关系。即是遍历 dp 表填表的过程中的 i, j对应原数组的值是 nums[i- 1][j - 1] 要注意后面还会再强调一遍。 3. 初始化
细节问题: 观察状态转移方程可知, 有可能会有越界的风险, 此处我们依旧采取一种多加一行一列的方式来进行初始化.多加一行一列要保证两点:
虚拟节点的值要保证后面的dp 表里的值是正确的要注意下标的映射关系. 因为我们是多加了一行一列, 所以对应到原始数组就应该行列要减一. (此处用到了原数组, 所以要有这个映射关系)
注意 这道题的初始化和前两道题有些许不同
原本的dp[0][0] 最小的路径和就是本身自己, 也就是 dp[0][0] nums[0][0]. 因为我们多加了一行一列, 所以变成了 dp[1][1] nums[0][0].观察下图我们发现填写 dp[1][1] 的时候需要用到左边和上边值 因为求的是二者中的最小值 为了不干扰结果 设置为0即可。看下图但是填写 dp[1][2] 的时候需要用到上面的值 dp[0][2] 和 dp[1][1] 作比较求最小值倘如是dp[1][2] 还是默认初始化为 0 的话 就会影响结果使dp[1][2] dp[0][2] nums[0][1], 导致错误了.dp[1][2] 本该是只有一条路径 那就是用到 11走到12就应该是 dp[1][2] dp[1][1] nums[0][1]. 观察结果让 dp[0][2] 是一个非常大的数字不影响结果即可。此处通常我们设置为整数最大值或者 0x3f3f3f3f.
看图更容易理解 4. 填表顺序
观察可知, 填 (i, j) 的值的时候需要用到上一行和左边的值. 所以填表顺序是 从上往下, 从左往右.
5. 返回值
根据题目的要求, 要到达(m, n) 最小路径和是多少, 正好对应 dp[m][n] 的表示. 所以返回 dp[m][n] 即可.
2. 代码
动态规划的代码编写一般都是分为 4 个步骤进行:
创建 dp 表初始化填表返回值 // 动态规划// 是不同路径1 的小幅改动版版: https://leetcode.cn/problems/unique-paths/public int uniquePathsWithObstacles(int[][] ob) {// 1.创建 dp表// 2.初始化// 3.填表// 4.返回值// 动态规划 这里的是二维, 所以时空都是O(M*N)int m ob.length, n ob[0].length;int[][] dp new int[m 1][n 1];// dp[1][1] 1;dp[0][1] 1;// 做好映射关系, 原数组的(0,0) 对应dp表中的(1,1)// 这里填的是 dp 表, 所以建议从(1,1) 开始, 也就是dp表多加了一行一列// 如果是障碍的话, 就直接忽略, 默认就是 0, 也就是表示到不了for(int i 1; i m; i) { // 从上往下每一行for(int j 1; j n; j) { // 从左往右每一列if(ob[i - 1][j - 1] 0) {dp[i][j] dp[i - 1][j] dp[i][j - 1];}}}return dp[m][n];}️️️ 好啦到这里有关本题的分享就没了如果感觉做的还不错的话可以点个赞关注一下你的支持就是我继续下去的动力我们下期再见拜了个拜~ ☆*: .. o(≧▽≦)o ..:*☆
