专做机械零配件的网站,易企秀在线制作免费,空压机网站开发公司,互联网创业项目平台专栏#xff1a;算法的魔法世界 个人主页#xff1a;手握风云 一、例题讲解
1.1. 不同路径 题目要求是计算从网格的左上角#xff08;起点#xff09;到右下角#xff08;终点#xff09;的所有不同路径的数量。机器人每次只能向下或向右移动一步。如下图所示#xff0… 专栏算法的魔法世界 个人主页手握风云 一、例题讲解
1.1. 不同路径 题目要求是计算从网格的左上角起点到右下角终点的所有不同路径的数量。机器人每次只能向下或向右移动一步。如下图所示在3*2的网格中机器人可以“向右、向下、向下”“向下、向下、向右”“向下、向右、向下”一共三种路径。 根据题目要求本题的状态表示为走到[i, j]为终点的位置时一共有多少种走法。因为机器人只能向下或者向右走那么我们要想知道[i, j]的路径数量就需要直到从起点到达[i-1, j]的路径数和[i, j-1]的路径数然后再向右走一步或者向下走一步就可以了。注意这是只是走了一步而不是走了一个路径。所以状态转移方程为dp[i][j] dp[i-1][j] dp[i][j-1]。根据状态转移方程我们需要根据左侧和上侧的网格来计算如下图所示的几个边界会出现越界的情况。我们仍然可以按照一维数组的方法增加虚拟节点。接下来就是要填写虚拟节点里的值保证后面填表的结果是正确的。填表顺序从上到下填写每一行从左到右填写每一列。 完整代码实现
class Solution {public int uniquePaths(int m, int n) {// 创建一个二维数组dp用于存储到达每个位置的路径数int[][] dp new int[m 1][n 1];// 初始化第一列的路径数为1因为只能从上往下走dp[0][1] 1;for (int i 1; i m; i) {for (int j 1; j n; j) {// 当前位置的路径数等于上方位置的路径数加上左方位置的路径数dp[i][j] dp[i - 1][j] dp[i][j - 1];}}return dp[m][n];}
}
1.2. 不同路径 II 本题与上一题一样计算不同的路径数每次只能向右或向下移动一步但某些网格是禁止通行的。 状态表示与上一题一样同样是走到[i, j]为终点的位置时一共有多少种走法。这里因为多了障碍物如果有障碍物的网格那么可到达的路径数就是0如果没有障碍物那么状态转移方程就是dp[i][j] dp[i-1][j] dp[i][j-1]。如果终点的左侧或者上侧有障碍物我们根本过不来路径数为0最后的相加的结果也没影响。初始化与上一题的方法一样我们只需要保证起点的值正确就可以。这里与上一题不同的是上一题的参数是两个整数这道题是一个二维数组需要注意下标的映射原始数组的下标与填表时的下标是[i-1][j-1]。填表顺序从上到下每一行从左到右。 完整代码实现
class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m obstacleGrid.length;int n obstacleGrid[0].length;// 创建一个二维数组dp用于存储到达每个位置的路径数int[][] dp new int[m 1][n 1];// 初始化dp[1][0]为1表示从起点到第一列的路径数dp[1][0] 1;for (int i 1; i m; i) {for (int j 1; j n; j) {// 如果当前位置没有障碍物则路径数等于上方和左方位置的路径数之和if (obstacleGrid[i - 1][j - 1] 0) {dp[i][j] dp[i - 1][j] dp[i][j - 1];}}}// 返回到达终点的路径数return dp[m][n];}
}
1.3. 珠宝的最高价值 题目要求在一个二维矩阵中从左上角开始每次只能向右或向下移动直到到达右下角找出一条路径使得路径上珠宝的总价值最大。 首先根据题目要求本题的状态表示为到达[i, j]位置时此时珠宝的最大价值。状态表示就是通过最近的一步来分析问题到达[i, j]的前一个位置[i-1, j]、[i, j-1]的珠宝最大价值再加上当前珠宝的价值所以状态转移方程dp[i][j] Math.max(dp[i][j - 1], dp[i - 1][j]) frame[i - 1][j - 1]。初始化的时候与上面一样保证不越界并且保证后面的填表是正确的因为我们是要左侧和上面之中的最大值因为珠宝的价值都是大于等于0的所以所有的都初始化为0。填表顺序从上到下每一行从左到右。 完整代码实现
class Solution {public int jewelleryValue(int[][] frame) {// 获取框架的行数和列数int m frame.length;int n frame[0].length;// 创建一个二维数组dp用于存储每个位置的最大珠宝价值int[][] dp new int[m 1][n 1];// 遍历框架的每个位置for (int i 1; i m; i) {for (int j 1; j n; j) {// 当前位置的最大珠宝价值等于当前位置的珠宝价值加上当前位置左边或上边的最大珠宝价值dp[i][j] Math.max(dp[i][j - 1], dp[i - 1][j]) frame[i - 1][j - 1];}}// 返回框架右下角的最大珠宝价值return dp[m][n];}
}
1.4. 下降路径最小和 给定一个包含整数的二维数组 matrix要求找到从第一行下降到最后一行的最小路径和。每次下降只能从当前元素移动到下一行的左上、正下、右下三个方向之一。具体来说对于矩阵中的每个元素matrix[i][j]你可以选择移动到matrix[i1][j-1]、matrix[i1][j]或matrix[i1][j1]并且需要保证这些移动是在矩阵的范围内。目标是找到从第一行任意元素开始经过若干次下降后到达最后一行的路径中路径和最小的值。 根据题目要求本题的状态表示为dp[i][j]到达[i,j]位置时的最小下降路径。接下来根据最近的一步划分问题如下图所示可以从A、B、C到达最后一行那么此时的最小路径和分别为dp[i-1][j-1](表示为x)、dp[i-1][j](表示为y)、dp[i-1][j1](表示为z)到达最后一行的状态表示dp[i][j]为前一个位置的最小路径和再加上它本身所以状态转移方程为dp[i][j]min(x,y,z)matrix[i][j]。 根据状态转移方程下图中的几个位置会发生越界。我们可以将dp表新增一行二列根据状态转移方程新增前第一行dp表的值都为0新增后第一行dp表的初始值也为0。为了不影响下一行的填表必须保证最左侧和最右侧的两列不参与运算我们可以将两列都初始化为无穷大。下标映射的时候为了对应原始矩阵的下标我们需要加上一行和两列我们一开始就把dp表都初始化为无穷大然后再把第一行改为0。填表的时候从上往下即可不用关心每一行的顺序。返回值要注意我们只需返回最后一行的最小值即可。 完整代码实现
class Solution {public int minFallingPathSum(int[][] matrix) {int n matrix.length;// 创建一个二维数组dp用于存储到达每个位置的最小路径和int[][] dp new int[n 1][n 2];// 将dp的第一行和最后一行初始化为最大值表示无法到达这些位置for (int i 1; i n; i) {dp[i][0] dp[i][n 1] Integer.MAX_VALUE;}for (int i 1; i n; i) {for (int j 1; j n; j) {// 计算到达当前位置的最小路径和dp[i][j] Math.min(dp[i - 1][j], Math.min(dp[i - 1][j - 1], dp[i - 1][j 1])) matrix[i - 1][j - 1];}}// 初始化最小路径和为最大值int ret Integer.MAX_VALUE;// 遍历dp的最后一行找到最小路径和for (int i 1; i n; i) {ret Math.min(ret, dp[n][i]);}return ret;}
}
1.5. 最小路径和 给定一个包含非负整数的 m x n 网格 grid找出一条从左上角到右下角的路径使得路径上的数字总和为最小。每次只能向下或者向右移动一步。返回一个整数表示所有可能路径中的最小和。 根据题目要求本题的状态表示为到达[i,j]位置时最小的路径和dp[i][j]。根据最近的一步到达这个终点位置的前一步为它的左侧和上方那么状态转移方程dp[i][j] min(dp[i - 1][j], dp[i][j - 1]) grid[i][j]。根据状态转移方程下图当中的几个位置会发生越界。为了不影响起点位置的值我们可以将起点位置的左侧和上方都初始化为0但起点位置的右上方不能初始化为0因为起点位置的右侧必须要取最小值所以我们可以将新增的都初始化为无穷大再将dp[0][1]和dp[1][0]赋值为0。填表顺序为从上到下每一行从左到右。返回值直接返回右下角的元素。 完整代码实现
class Solution {public int minPathSum(int[][] grid) {// 获取网格的行数和列数int m grid.length;int n grid[0].length;// 创建一个二维数组dp用于存储到达每个位置的最小路径和int[][] dp new int[m 1][n 1];for (int i 0; i m; i) {dp[i][0] Integer.MAX_VALUE;}for (int i 0; i n; i) {dp[0][i] Integer.MAX_VALUE;}// 初始化dp数组的起点位置表示从起点到起点的最小路径和为0dp[0][1] dp[1][0] 0;for (int i 1; i m; i) {for (int j 1; j n; j) {// 到达当前位置的最小路径和等于到达上方位置和左方位置的最小路径和加上当前位置的值dp[i][j] Math.min(dp[i - 1][j], dp[i][j - 1]) grid[i - 1][j - 1];}}return dp[m][n];}
}
1.6. 地下城游戏 给定一个二维的地下城其中每个格子代表勇士的血量增减。勇士从左上角出发需要到达右下角的公主所在的格子。勇士在任何时候的血量都不能小于1。请你计算出勇士初始需要的最小血量。 我们根据示例1推导一下初始血量假设初始血量HP为3才能走出第一个房间但走不出第二个房间假设HP为6时能够走出前两个房间接着吃血包恢复到5但走到最后右下角房间时血量为0还是无法救出公主因此初始血量必须为7。 根据前面几题的经验和题目要求1. 以右下角为结尾从起点出发到达[i, j]位置时的最低HP。但我们这样定义状态表示是不行的因为根据示例1的分析状态表示不光受到前面状态的影响也会受到后面状态的影响填表的时候也得需要后面路径选择的影响。2. 反过来以左上角为起点从[i, j]到达起点所需最低的HP。 接下来根据最近的一步划分问题设初始血量为x当骑士向下走或者向右走的时候我们需要保证他走出这个房间之后HP大于等于最低HP要求也就是状态转移方程dp[i][j] min(dp[i 1][j] - dungeon[i][j], dp[i][j 1] - dungeon[i][j])。但还有一个细节需要注意如果dungeon[i][j]太大一减成了负数骑士提前死亡无法吃到血包。所以我们还需要对max(dungeon[i][j],1)。 初始化的时候根据状态转移方程下图这些位置会越界并且我们只需保证填表正确即可不需要关注下标的映射关系。填表顺序从下往上填每一行每一行从右往左。返回值dp[0][0]。 完整代码实现
class Solution {public int calculateMinimumHP(int[][] dungeon) {// 获取地图的行数和列数int m dungeon.length, n dungeon[0].length;// 创建一个二维数组dp用于存储从起点到每个点的最小生命值int[][] dp new int[m 1][n 1];// 将dp数组的最后一行和最后一列初始化为最大值for (int i 0; i n; i) {dp[m][i] Integer.MAX_VALUE;}for (int i 0; i m; i) {dp[i][n] Integer.MAX_VALUE;}// 将dp数组的倒数第二行和倒数第二列初始化为1dp[m][n - 1] dp[m - 1][n] 1;// 从倒数第二行和倒数第二列开始逐行逐列计算每个点的最小生命值for (int i m - 1; i 0; i--) {for (int j n - 1; j 0; j--) {// 当前点的最小生命值为从右边和下边的最小生命值减去当前点的值dp[i][j] Math.min(dp[i][j 1], dp[i 1][j]) - dungeon[i][j];// 如果当前点的最小生命值小于1则将其设置为1dp[i][j] Math.max(dp[i][j], 1);}}// 返回起点处的最小生命值return dp[0][0];}
}
