营销型网站重要性,电子商务网站建设与管理目录,数字展厅网站建设,产品设计论文1.不同路径
62. 不同路径
一个机器人位于一个 m x n 网格的左上角 #xff08;起始点在下图中标记为 “Start” #xff09;。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角#xff08;在下图中标记为 “Finish”
问总共有多少条不同的路径
因为题…1.不同路径
62. 不同路径
一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish”
问总共有多少条不同的路径
因为题给信息一维数组已经完成不了要求所以我们要用二维数组
1.状态表示用dp[ i ][ j ]表示以第 i 行 j 列为结尾的路径总和
2.状态转移方程dp[ i ][ j ] dp[ i - 1][ j ] dp[ i ][ j - 1 ]
3.初始化dp[0][1] 1
4.填表顺序从上往下填每一行从左往右填每一列
5.返回值dp[m][n]
class Solution {
public:int uniquePaths(int m, int n) {//1. 创建 dp 表//2. 初始化//3. 填表//4. 返回值vectorvectorint dp(m 1, vectorint(n 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];}
};
这是ac代码
2.不同路径II
63. 不同路径 II
一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish”。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径
网格中的障碍物和空位置分别用 1 和 0 来表示
1.状态表示用dp[ i ][ j ]表示以第 i 行 j 列为结尾的路径总和
2.状态转移方程dp[ i ][ j ] dp[ i - 1][ j ] dp[ i ][ j - 1 ]
3.初始化dp[0][1] 1
4.填表顺序从上往下填每一行从左往右填每一列
5.返回值dp[m][n]
这题与前面的题相似要注意当位置为障碍物时dp[ i ][ j ] 的值应该为0
class Solution {
public:int uniquePathsWithObstacles(vectorvectorint obstacleGrid) {int m obstacleGrid.size();int n obstacleGrid[0].size();vectorvectorint dp(m 1, vectorint(n 1));dp[0][1] 1;for(int i 1; i m ; i)for(int j 1; j n; j){if(obstacleGrid[i - 1][j - 1])dp[i][j] 0;elsedp[i][j] dp[i - 1][j] dp[i][j - 1];}return dp[m][n];}
};
这是ac代码
3.珠宝的最大价值
LCR 166. 珠宝的最高价值
现有一个记作二维矩阵 frame 的珠宝架其中 frame[i][j] 为该位置珠宝的价值。拿取珠宝的规则为
只能从架子的左上角开始拿珠宝每次可以移动到右侧或下侧的相邻位置到达珠宝架子的右下角时停止拿取
1.状态表示用dp[ i ][ j ]表示以第 i 行 j 列为结尾的最大礼物价值
2.状态转移方程dp[ i ][ j ] max( dp[ i - 1][ j ], dp[ i ][ j - 1 ] ) p[ i ][ j ]
3.初始化
4.填表顺序从上往下填每一行从左往右填每一列
5.返回值dp[m][n]
注意开vector时每行每列多开一行列所以找对应p时要注意下标映射关系
class Solution {
public:int jewelleryValue(vectorvectorint frame) {int m frame.size();int n frame[0].size();vectorvectorint dp(m 1, vectorint(n 1));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]) frame[i - 1][j - 1];return dp[m][n];}
};
这是ac代码
4.下降路径最小和
931. 下降路径最小和
给你一个 n x n 的 方形 整数数组 matrix 请你找出并返回通过 matrix 的下降路径 的 最小和 。
下降路径 可以从第一行中的任何元素开始并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列即位于正下方或者沿对角线向左或者向右的第一个元素。具体来说位置 (row, col) 的下一个元素应当是 (row 1, col - 1)、(row 1, col) 或者 (row 1, col 1)
1.状态表示用dp[ i ][ j ]表示以第 i 行 j 列为结尾的下降路径最小和
2.状态转移方程dp[ i ][ j ] min( dp[ i - 1][ j ], dp[ i - 1][ j - 1 ] , dp[ i - 1 ][ j 1 ]) p[ i ][ j ]
3.初始化 第一行全为0 其他全为INT_MAX
4.填表顺序从上往下填每一行从左往右填每一列
5.返回值最后一行的最小值
注意 下标的映射关系开数组的大小返回值的判断
class Solution {
public:int minFallingPathSum(vectorvectorint matrix){ int n matrix.size();vectorvectorint dp(n 1, vectorint(n 2, INT_MAX));for(int j 0; j n 2; j)dp[0][j] 0;for(int i 1; i n; i)for(int j 1; j n; j)dp[i][j] min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i - 1][j 1])) matrix[i - 1][j - 1];int ret INT_MAX;for(int j 1; j n; j)ret min(ret, dp[n][j]);return ret;}
};
这是ac代码
5.最小路径和
64. 最小路径和
给定一个包含非负整数的 m x n 网格 grid 请找出一条从左上角到右下角的路径使得路径上的数字总和为最小。
说明每次只能向下或者向右移动一步
1.状态表示用dp[ i ][ j ]表示以第 i 行 j 列为结尾的路径最小和
2.状态转移方程dp[ i ][ j ] min( dp[ i - 1][ j ], dp[ i ][ j - 1 ]) p[ i ][ j ]
3.初始化 dp[0][1] 0, 其他全为INT_MAX
4.填表顺序从上往下填每一行从左往右填每一列
5.返回值dp[m][n]
注意下标的映射关系数组的初始化
class Solution {
public:int minPathSum(vectorvectorint grid) {int m grid.size();int n grid[0].size();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];}
};
这是ac代码
6.地下城游戏
174. 地下城游戏
恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下他会立即死亡。
有些房间由恶魔守卫因此骑士在进入这些房间时会失去健康点数若房间里的值为负整数则表示骑士将损失健康点数其他房间要么是空的房间里的值为 0要么包含增加骑士健康点数的魔法球若房间里的值为正整数则表示骑士将增加健康点数。
为了尽快解救公主骑士决定每次只 向右 或 向下 移动一步。
返回确保骑士能够拯救到公主所需的最低初始健康点数。
注意任何房间都可能对骑士的健康点数造成威胁也可能增加骑士的健康点数包括骑士进入的左上角房间以及公主被监禁的右下角房间
1.状态表示用dp[ i ][ j ]表示以第 i 行 j 列为开始的所需最小生命值
2.状态转移方程dp[ i ][ j ] min( dp[ i 1][ j ], dp[ i ][ j 1 ]) - p[ i ][ j ]
3.初始化 dp[m][n - 1] 0, 其他全为INT_MAX
4.填表顺序从下往上填每一行从右往左填每一列
5.返回值dp[0][0]
注意初始化和填表顺序状态转移方程当dp[ i ][ j ] 1时下一个血包很大导致当前需要可能小于1我们要对1取max保证情况的正确性
class Solution {
public:int calculateMinimumHP(vectorvectorint dungeon) {int m dungeon.size();int n dungeon[0].size();vectorvectorint dp(m 1, vectorint(n 1, INT_MAX));dp[m - 1][n] 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];dp[i][j] max(dp[i][j], 1);}return dp[0][0];}
};
这是ac代码
新手写博客有不对的位置希望大佬们能够指出也谢谢大家能看到这里让我们一起学习进步吧
