泉州易尔通网站建设,国际酒店网站建设不好,安吉网站制作,北京做网站哪家公司好动态规划2.0 动态规划 - - - 路径问题1. 不同路径2. 不同路径Ⅱ3. 珠宝的最高价值4. 下降路径最小和5. 最小路径和6. 地下城游戏 动态规划 - - - 路径问题
1. 不同路径
题目链接 - Leetcode -62.不同路径
Leetcode -62.不同路径
题目#xff1a;一个机器人位于一个 m … 动态规划2.0 动态规划 - - - 路径问题1. 不同路径2. 不同路径Ⅱ3. 珠宝的最高价值4. 下降路径最小和5. 最小路径和6. 地下城游戏 动态规划 - - - 路径问题
1. 不同路径
题目链接 - Leetcode -62.不同路径
Leetcode -62.不同路径
题目一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish” 。 问总共有多少条不同的路径
示例 1 输入m 3, n 7 输出28
示例 2 输入m 3, n 2 输出3 解释 从左上角开始总共有 3 条路径可以到达右下角。
向右-向下-向下向下-向下-向右向下-向右-向下
示例 3 输入m 7, n 3 输出28
示例 4 输入m 3, n 3 输出6
提示
1 m, n 100题目数据保证答案小于等于 2 * 10^9
思路
状态表示对于这种「路径类」的问题我们的状态表示一般有两种形式 i. 从 [i, j] 位置出发… ii. 从起始位置出发到达 [i, j] 位置… 我们选择第二种定义状态表示的方式dp[i][j] 表示走到 [i, j] 位置处一共有多少种方式。状态转移方程分析一下如果 dp[i][j] 表示到达 [i, j] 位置的方法数那么到达 [i, j] 位置之前的一小步有两种情况 i. 从 [i, j] 位置的上方 [i - 1, j] 的位置向下走一步转移到 [i, j] 位置 ii. 从 [i, j] 位置的左方 [i, j - 1] 的位置向右走一步转移到 [i, j] 位置。 由于我们要求的是有多少种方法因此状态转移方程就呼之欲出了 dp[i][j] dp[i - 1][j] dp[i][j - 1] 。返回值根据状态表示我们要返回 dp[m][n] 的值。
代码如下 class Solution {public:int uniquePaths(int m, int n){// 多开一行一列可以直接在循环内初始化vectorvectorint dp(m 1, vectorint(n 1));dp[0][1] 1; // 为了后面填表的正确// dp[i][j] 表示⾛到 [i, j] 位置处⼀共有多少种方式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];}};2. 不同路径Ⅱ
题目链接 - Leetcode -63.不同路径Ⅱ
Leetcode -63.不同路径Ⅱ
题目一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish”。 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径 网格中的障碍物和空位置分别用 1 和 0 来表示。
示例 1 输入obstacleGrid [[0, 0, 0], [0, 1, 0], [0, 0, 0]] 输出2 解释3x3 网格的正中间有一个障碍物。 从左上角到右下角一共有 2 条不同的路径
向右-向右-向下-向下向下-向下-向右-向右
示例 2 输入obstacleGrid [[0, 1], [0, 0]] 输出1
提示
m obstacleGrid.lengthn obstacleGrid[i].length1 m, n 100obstacleGrid[i][j] 为 0 或 1
思路本题为不同路径的变型只不过有些地方有「障碍物」只要在「状态转移」上稍加修改就可解决。
状态表示dp[i][j] 表示走到 [i, j] 位置处一共有多少种方式。状态转移简单分析一下。如果 dp[i][j] 表示到达 [i, j] 位置的方法数那么到达 [i, j] 位置之前的一小步有两种情况 i. 从 [i, j] 位置的上方 [i - 1, j] 的位置向下走一步转移到 [i, j] 位置 ii. 从 [i, j] 位置的左方 [i, j - 1] 的位置向右走一步转移到 [i, j] 位置。 但是 [i - 1, j] 与 [i, j - 1] 位置都是可能有障碍的此时从上面或者左边是不可能到达 [i, j] 位置的也就是说此时的方法数应该是 0由此我们可以得出一个结论只要这个位置上「有障碍物」那么我们就不需要计算这个位置上的值直接让它等于 0 即可。返回值根据状态表示我们要返回的结果是 dp[m][n].
代码如下 class Solution {public:int uniquePathsWithObstacles(vectorvectorint obstacleGrid){int m obstacleGrid.size(), n obstacleGrid[0].size();// 多开一行一列方便初始化vectorvectorint dp(m 1, vectorint(n 1));dp[0][1] 1; // 为了后面填表的正确// dp[i][j] 表示⾛到 [i, j] 位置处⼀共有多少种方式for (int i 1; i m; i){for (int j 1; j n; j){// 原矩阵中的位置不是障碍物if (obstacleGrid[i - 1][j - 1] ! 1){dp[i][j] dp[i - 1][j] dp[i][j - 1];}}}return dp[m][n];}};3. 珠宝的最高价值
题目链接 - Leetcode -LCR 166.珠宝的最高价值
Leetcode -LCR 166.珠宝的最高价值
题目现有一个记作二维矩阵 frame 的珠宝架其中 frame[i][j] 为该位置珠宝的价值。拿取珠宝的规则为
只能从架子的左上角开始拿珠宝 每次可以移动到右侧或下侧的相邻位置 到达珠宝架子的右下角时停止拿取 注意珠宝的价值都是大于 0 的。除非这个架子上没有任何珠宝比如 frame [[0]] 。
示例 1: 输入: frame [[1, 3, 1], [1, 5, 1], [4, 2, 1]] 输出 : 12 解释 : 路径 1→3→5→2→1 可以拿到最高价值的珠宝
提示
0 frame.length 2000 frame[0].length 200
思路本题的思路与上题的思路差不多状态转移方程为dp[i][j] max(dp[i - 1][j], dp[i][j - 1]) grid[i][j] .
代码如下 class Solution {public:int maxValue(vectorvectorint grid){int m grid.size(), n grid[0].size();// 多开一行一列方便初始化vectorvectorint dp(m 1, vectorint(n 1));// dp[i][j] 表示⾛到 [i, j] 位置处此时的最大价值for (int i 1; i m; i){for (int j 1; j n; j){dp[i][j] max(dp[i - 1][j], dp[i][j - 1]) grid[i - 1][j - 1];}}return dp[m][n];}};4. 下降路径最小和
题目链接 - Leetcode -931.下降路径最小和
Leetcode -931.下降路径最小和
题目给你一个 n x n 的 方形 整数数组 matrix 请你找出并返回通过 matrix 的下降路径 的 最小和 。
下降路径 可以从第一行中的任何元素开始并从每一行中选择一个元素。 在下一行选择的元素和当前行所选元素最多相隔一列即位于正下方或者沿对角线向左或者向右的第一个元素。 具体来说位置(row, col) 的下一个元素应当是(row 1, col - 1)、(row 1, col) 或者(row 1, col 1) 。
示例 1 输入matrix [[2, 1, 3], [6, 5, 4], [7, 8, 9]] 输出13 解释如图所示为和最小的两条下降路径
示例 2 输入matrix [[-19, 57], [-40, -5]] 输出 - 59 解释如图所示为和最小的下降路径 提示
n matrix.length matrix[i].length1 n 100100 matrix[i][j] 100
思路
状态表示dp[i][j] 表示到达 [i, j] 位置时所有下降路径中的最小和。状态转移方程对于普遍位置 [i, j] 根据题意得到达 [i, j] 位置可能有三种情况 i. 从正上方 [i - 1, j] 位置转移到 [i, j] 位置 ii. 从左上方 [i - 1, j - 1] 位置转移到 [i, j] 位置 iii. 从右上方 [i - 1, j 1] 位置转移到 [i, j] 位置 我们要的是三种情况下的「最小值」然后再加上矩阵在 [i, j] 位置的值。 于是 dp[i][j] min(dp[i - 1][j], min(dp[i - 1][j - 1], dp[i - 1][j 1])) matrix[i][j] 。返回值注意这里不是返回 dp[m][n] 的值题目要求「只要到达最后一行」就行了因此这里应该返回「 dp 表中最后一行的最小值」。
代码如下 class Solution {public:int minFallingPathSum(vectorvectorint matrix){int len matrix.size();// 多开一行两列因为dp[i][j]的值需要用到dp[i - 1][j], dp[i - 1][j - 1], dp[i - 1][j 1]vectorvectorint dp(len 1, vectorint(len 2, INT_MAX));// 初始化为了后面填表的正确性for (int i 0; i len; i) dp[0][i] 0;// dp[i][j] 表示到达 [i, j] 位置时所有下降路径中的最小和for (int i 1; i len; i){for (int j 1; j len; j){dp[i][j] min(min(dp[i - 1][j], dp[i - 1][j - 1]), dp[i - 1][j 1]) matrix[i - 1][j - 1];}}// 返回最后一行的最小值int ret INT_MAX;for (int j 0; j len; j) ret min(ret, dp[len][j]);return ret;}};5. 最小路径和
题目链接 - Leetcode -64.最小路径和
Leetcode -64.最小路径和
题目给定一个包含非负整数的 m x n 网格 grid 请找出一条从左上角到右下角的路径使得路径上的数字总和为最小。
说明每次只能向下或者向右移动一步。
示例 1 输入grid [[1, 3, 1], [1, 5, 1], [4, 2, 1]] 输出7 解释因为路径 1→3→1→1→1 的总和最小。
示例 2 输入grid [[1, 2, 3], [4, 5, 6]] 输出12
提示
m grid.lengthn grid[i].length1 m, n 2000 grid[i][j] 200
思路
状态表示dp[i][j] 表示到达 [i, j] 位置处最小路径和是多少状态转移分析一下如果 dp[i][j] 表示到达 [i, j] 位置处的最小路径和那么到达[i, j] 位置之前的一小步有两种情况 i. 从 [i - 1, j] 向下走一步转移到 [i, j] 位置 ii. 从 [i, j - 1] 向右走一步转移到 [i, j] 位置。 由于到 [i, j] 位置两种情况并且我们要找的是最小路径因此只需要这两种情况下的最小值再加上 [i, j] 位置上本身的值即可。也就是 dp[i][j] min(dp[i - 1][j], dp[i][j - 1]) grid[i][j]返回值根据状态表示我们要返回的结果是 dp[m][n].
代码如下 class Solution {public:int minPathSum(vectorvectorint grid){int m grid.size(), n grid[0].size();// dp[i][j] 表示到达 [i, j] 位置处最小路径和是多少vectorvectorint dp(m 1, vectorint(n 1, INT_MAX));dp[0][1] 0;for (int i 1; i m; i){for (int j 1; j n; j){dp[i][j] min(dp[i - 1][j], dp[i][j - 1]) grid[i - 1][j - 1];}}return dp[m][n];}};6. 地下城游戏
题目链接 - Leetcode -174.地下城游戏
Leetcode -174.地下城游戏
题目恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。 我们英勇的骑士最初被安置在 左上角 的房间里他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下他会立即死亡。
有些房间由恶魔守卫因此骑士在进入这些房间时会失去健康点数若房间里的值为负整数则表示骑士将损失健康点数 其他房间要么是空的房间里的值为 0要么包含增加骑士健康点数的魔法球若房间里的值为正整数则表示骑士将增加健康点数。 为了尽快解救公主骑士决定每次只 向右 或 向下 移动一步。 返回确保骑士能够拯救到公主所需的最低初始健康点数。 注意任何房间都可能对骑士的健康点数造成威胁也可能增加骑士的健康点数包括骑士进入的左上角房间以及公主被监禁的右下角房间。
示例 1 输入dungeon [[-2, -3, 3], [-5, -10, 1], [10, 30, -5]] 输出7 解释如果骑士遵循最佳路径右-右-下-下 则骑士的初始健康点数至少为 7 。
示例 2 输入dungeon [[0]] 输出1
提示
m dungeon.lengthn dungeon[i].length1 m, n 2001000 dungeon[i][j] 1000
思路
状态表示这道题如果我们定义成从起点开始到达 [i, j] 位置的时候所需的最低初始健康点数。那么我们分析状态转移的时候会有一个问题那就是我们当前的健康点数还会受到后面的路径的影响。也就是从上往下的状态转移不能很好地解决问题。 这个时候我们要换一种状态表示从 [i, j] 位置出发到达终点时所需要的最低初始健康点数。这样我们在分析状态转移的时候后续的最佳状态就已经知晓。综上所述定义状态表示为dp[i][j] 表示从 [i, j] 位置出发到达终点时所需的最低初始健康点数。状态转移方程对于 dp[i][j] 从 [i, j] 位置出发下一步会有两种选择为了方便理解设 dp[i][j] 的最终答案是 x i. 走到右边然后走向终点那么我们在 [i, j] 位置的最低健康点数加上这一个位置的消耗应该要大于等于右边位置的最低健康点数也就是 x dungeon[i][j] dp[i][j 1] 通过移项可得 x dp[i][j 1] - dungeon[i][j] 。因为我们要的是最小 值因此这种情况下的 x dp[i][j 1] - dungeon[i][j] ii. 走到下边然后走向终点那么我们在 [i, j] 位置的最低健康点数加上这⼀个位置的消耗应该要大于等于下边位置的最低健康点数也就是 x dungeon[i][j] dp[i 1][j] 。通过移项可得 x dp[i 1][j] - dungeon[i][j] 。因为我们要的是最小值因此这种情况下的 x dp[i 1][j] - dungeon[i][j]
综上所述我们需要的是两种情况下的最小值因此可得状态转移方程为dp[i][j] min(dp[i 1][j], dp[i][j 1]) - dungeon[i][j]
但是如果当前位置的 dungeon[i][j] 是一个比较大的正数的话 dp[i][j] 的值可能变成 0 或者负数。也就是最低点数会小于 1 那么骑士就会死亡。因此我们求出来的 dp[i][j] 如果小于等于 0 的话说明此时的最低初始值应该为 1 。处理这种情况仅需让 dp[i][j] 与 1 取一个最大值即可dp[i][j] max(1, dp[i][j]) 初始化可以在最前面加上一个「辅助结点」帮助我们初始化。使用这种技巧要注意两个点 i. 辅助结点里面的值要「保证后续填表是正确的」 ii. 「下标的映射关系」。 在本题中在 dp 表最后面添加一行并且添加一列后所有的值都先初始化为无穷大然后让 dp[m][n - 1] dp[m - 1][n] 1 即可。 返回值根据「状态表示」我们需要返回 dp[0][0] 的值。
代码如下 class Solution {public:int calculateMinimumHP(vectorvectorint dungeon){int m dungeon.size(), n dungeon[0].size();vectorvectorint dp(m 1, vectorint(n 1, INT_MAX));dp[m][n - 1] 1;// 从右下角往回推for (int i m - 1; i 0; i--){for (int j n - 1; j 0; j--){dp[i][j] min(dp[i 1][j], dp[i][j 1]) - dungeon[i][j];// 如果减到负数说明这里的血包很大即使是负数到这里都可以但是这是不符合常理的// 所以需要将这里置成 1 即可if (dp[i][j] 0) dp[i][j] 1; }}// 返回最初位置return dp[0][0];}};
