陕西省建设厅申报网站,wordpress ftp 插件,wordpress扒站教程,网络舆情监测机制前言 作者#xff1a;小蜗牛向前冲 专栏#xff1a;小蜗牛算法之路 专栏介绍#xff1a;蜗牛之道#xff0c;攀登大厂高峰#xff0c;让我们携手学习算法。在这个专栏中#xff0c;将涵盖动态规划、贪心算法、回溯等高阶技巧#xff0c;不定期为你奉上基础数据结构… 前言 作者小蜗牛向前冲 专栏小蜗牛算法之路 专栏介绍蜗牛之道攀登大厂高峰让我们携手学习算法。在这个专栏中将涵盖动态规划、贪心算法、回溯等高阶技巧不定期为你奉上基础数据结构的精彩算法之旅。一同努力追逐技术的星辰大海。 目录
一、不同路径IImedium
a、解题思路
b、代码
二、礼物的最⼤价值medium
a、解题思路
b、代码
三、 下降路径最⼩和medium
a、解题思路
b、代码
四、 最⼩路径和medium
a、解题思路
b、代码
五、地下城游戏hard
a、解题思路
b、代码 本期继续手撕动态规划不同路径IImedium礼物的最⼤价值medium下降路径最⼩和medium最⼩路径和medium地下城游戏hard
继续刷动态规划相关算法题如果不清楚什么是动态规划的可以看这里[动态规划]---part1
一、不同路径IImedium 一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish”。 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径 网格中的障碍物和空位置分别用 1 和 0 来表示。 示例 1 输入obstacleGrid [[0,0,0],[0,1,0],[0,0,0]]
输出2
解释3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径
1. 向右 - 向右 - 向下 - 向下
2. 向下 - 向下 - 向右 - 向右示例 2 输入obstacleGrid [[0,1],[0,0]]
输出1提示 m obstacleGrid.lengthn obstacleGrid[i].length1 m, n 100obstacleGrid[i][j] 为 0 或 1 class Solution {
public:int uniquePathsWithObstacles(vectorvectorint obstacleGrid) {}
};
a、解题思路
这道题和同路径I的解题思路非常相似但是就是在机器人找 到终点的过程中会有障碍物。
1、转态表示
首先我们想以ij位置为结尾表示什么
dp[i][j表示以i,j位置结尾的时候机器人到这里有多少条路径 2、状态转移方程
根据最近的一个位置划分 当前位置有障碍物 返回0 当前位置没有障碍物 dp[i][j] dp[i-1][j]dp[i][j-1]; 大家可能会想我要是在[i-1][j]或者[i][j-1]遇到障碍物了状态转态方程还可以相加吗?
其实是可能的因为我在遇到障碍物是返回0的而0对相加的结果是没有影响的。
3、初始化 这里我们要初始化就是在二维数组多开一行和一列但我们要思路多开的行列填什么呢一切都是为了填表走服务很明显机器人是在[1,1]位置开始走的也就说[1,1]位置肯定要为1当最特色情况起点就是中点所以我们只要保证dp[1][0]1或者dp[0][1]1即可。其他位置看情况决定。
这里除了要注意填表的初始化还要注意下标映射关心的改变 obstacleGrid[0][0]--------映射dp[1][1]; obstacleGrid[2][3]--------映射dp[3][4]; 也就是横着纵坐标都要加1 4、 填表顺序
从上往下填写每一行每一行都是从左往又开始填写
5、返回值
dp[m][n]
b、代码
class Solution {
public:int uniquePathsWithObstacles(vectorvectorint obstacleGrid){int m obstacleGrid.size();//有多少行int n obstacleGrid[0].size();//有多少列//创建dp表vectorvectorint dp(m 1, vectorint(n 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] 1){dp[i][j] 0;}else{dp[i][j] dp[i][j - 1] dp[i-1][j];}}}//返回return dp[m][n];}
}; Leetcode 测试结果
二、礼物的最⼤价值medium 现有一个记作二维矩阵 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 class Solution {
public:int jewelleryValue(vectorvectorint frame) {}
};
a、解题思路
这种路径题目极大可能用动态规划求解
1、转态表示
首先我们想以ij位置为结尾表示什么
dp[i][j表示以i,j位置结尾的时候此时礼物的最大值 2、状态转移方程
根据最近的一个位置划分 从[i-1][j]------[i][j] 那礼物的不就是dp[i-1][j]frmae[i-1][j-1];frmae的坐标是映射过的 从[i][jj-1]------[i][j] 那礼物的不就是dp[i][j-1]frmae[i-1][j-1]; 但是我们要求的是拿到礼物的最大值 状态转移方程dp[i][jj max(dp[i-1][j],dp[i][j-1])frmae[i][j]; 3、初始化 这里的初始化就非常简单了对应[1][1]位置我们肯定是要保证他在填表的时候不变的那么[1][0]和[0][1]位置肯定是0,至于0行0列后面的按理来说是要初始化为负无穷的但因为礼物值0所以初始化为0也可以。(这里就不用我们初始化了因为vector是有初始化功能的)
4、 填表顺序
从上往下填写每一行每一行都是从左往又开始填写
5、返回值
dp[m][n]
b、代码
class Solution {
public:int jewelleryValue(vectorvectorint frame){int m frame.size();//行int n frame[0].size();//列//创建dp表vectorvectorint dp(m1,vectorint(n1));//初始化vector已经完成//填表for(int i 1;im;i){for(int j 1;jn;j){dp[i][j] max(dp[i-1][j],dp[i][j-1]) frame[i-1][j-1];}}return dp[m][n];}
}; Leetcode 测试结果
三、 下降路径最⼩和medium 给你一个 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 100-100 matrix[i][j] 100 class Solution {
public:int minFallingPathSum(vectorvectorint matrix) {}
}; a、解题思路
上面我们刚刚做完最大价值现在来做最小和二者思路非常相似但是我们这里要仔细读题。
1、转态表示 dp[i][j]表示到达[i,j]位置时最小的下降路径 2、状态转移方程
根据最近的一个位置划分 从[i-1][j-1]------[i][j] 那最小的下降路径不就是dp[i-1][j-1]m[i][j; 从[i][jj-1]------[i][j] 那最小的下降路径不就是dp[i-1][j]m[i][j; 从[i]-1[jj]------[i][j] 那最小的下降路径不就是dp[i-1][j1]m[i][j; 但是我们要求的是最小的下降路径 状态转移方程dp[i][jj min(x,y,z)m[i][j]; 3、初始化
这里的初始化和前面有点不同所以我希望大家在做这种类型题目的时候不要无脑初始化一定要先进行分析。 首先我们肯定是其想是第一行位置的值 肯定是其本身最小的下降路径根据转态转移方程我们肯定是不能让我们新添加的行影响结果所以把第一行初始化为0。在选择dp[1][2]进行观测(不一定非要选择这个位置合适就好)根据转态转移方程我们肯定是不能让我们新添加的列影响结果所以要把第一列初始化为正无穷第一行元素除外在选择dp[1][3]进行观察根据转态转移方程我们肯定是不能让我们新添加的列影响结果所以要把最后一列初始化为正无穷第一行元素除外 4、 填表顺序
从上往下填写值到最后一行
5、返回值
返回最后一行的最小值
b、代码
class Solution {
public:int get_min(int x,int y,int z){int tmp min(x,y);return min(tmp,z);}int minFallingPathSum(vectorvectorint matrix){int m matrix.size();int n matrix[0].size();int max INT_MAX;//相当与正无穷//创建dp表vectorvectorint dp(m1,vectorint(n2,max));//初始化 这里初始化第一行就好for(int i 0;in2;i){dp[0][i] 0;}//填表for(int i 1;im;i){for(int j 1;jn;j){dp[i][j] get_min(dp[i-1][j-1],dp[i-1][j],dp[i-1][j1])matrix[i-1][j-1];}}//遍历最后一行找出最小值返回int min max;for(int i 1;in;i){if(dp[m][i]min) min dp[m][i];}return min;}
}; Leetcode 测试结果 四、 最⼩路径和medium 给定一个包含非负整数的 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 class Solution {
public:int minPathSum(vectorvectorint grid) {}
};
a、解题思路
又是这种路径的问题我相信如果大家认真做了前面的题这题思路就非常清晰了
1、转态表示 dp[i][j]表示到达[i,j]位置时最小的路径路径和 2、状态转移方程
根据最近的一个位置划分 从[i-1][j]------[i][j] 那最小路径和不就是dp[i-1][j]g[i][j]; 从[i][jj-1]------[i][j] 那最小的下降路径不就是dp[i][j-1]g[i][j]; 但是我们要求的是最小的下降路径 状态转移方程 dp[i][j] min(dp[i-1][j],dp[i][j-1])grid[i-1][j-1]; 3、初始化
还先分析第一个位置那么dp[0][1]和dp[1][0]就要初始化为0其他位置我们想现在可以总结一下了 当求最小值 就初始化为正无尽当求最大值 就初始化为负无尽 4、 填表顺序
从上往下填写在从左往右。
5、返回值
dp[m][n]
b、代码
class Solution {
public:int minPathSum(vectorvectorint grid){int m grid.size();int n grid[0].size();//创建dpvectorvectorint dp(m1,vectorint(n1,INT_MAX));//初始化dp[1][0] dp[0][1] 0;//填表for(int i 1;im;i){for(int j 1;jn;j){dp[i][j] min(dp[i-1][j],dp[i][j-1])grid[i-1][j-1];}}//返回return dp[m][n];}
}; Leetcode 测试结果 五、地下城游戏hard 恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里他必须穿过地下城并通过对抗恶魔来拯救公主。 骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下他会立即死亡。 有些房间由恶魔守卫因此骑士在进入这些房间时会失去健康点数若房间里的值为负整数则表示骑士将损失健康点数其他房间要么是空的房间里的值为 0要么包含增加骑士健康点数的魔法球若房间里的值为正整数则表示骑士将增加健康点数。 为了尽快解救公主骑士决定每次只 向右 或 向下 移动一步。 返回确保骑士能够拯救到公主所需的最低初始健康点数。 注意任何房间都可能对骑士的健康点数造成威胁也可能增加骑士的健康点数包括骑士进入的左上角房间以及公主被监禁的右下角房间。 示例 1 输入dungeon [[-2,-3,3],[-5,-10,1],[10,30,-5]]
输出7
解释如果骑士遵循最佳路径右 - 右 - 下 - 下 则骑士的初始健康点数至少为 7 。 示例 2 输入dungeon [[0]]
输出1 class Solution {
public:int calculateMinimumHP(vectorvectorint dungeon) {}
};
a、解题思路
大家遇到这种文字多的题目不要害怕如果读不明白就带这例题求推就好了。 1、转态表示 大家可能非常想到是以某一个位置结尾推出 dp[i][j]表示到达[i,j]位置时所需的最低血量点数。但这是不正确的因为我们不仅仅在[i][j]位置受到前面位置的影响其实我们还会受到后面位置的影响所以这样的转态表示是不可取的。
但是我们还可以想 一下以某位置为起点来推
dp[i][j]表示从[i,j]位置重出发到达终点所要的最低健康血量 2、状态转移方程
根据最近的一个位置划分 往右走那最低血量应该是dp[i][j1] -d[i][j] 往下走那最低血量应该是dp[i]1[j] -d[i][j] 但是我们还要注意当d[i][j]此时非常大的时候dp[i][j]可能出现负值但是这样是不符合常理的所以我们要处理一下dp[i][j] max(1,dp[i][j]); 到达终点所要的最低健康血量 状态转移方程 dp[i][j] min(dp[i][j1],dp[i1][j])d[i][j];
3、初始化
这里我们填表因为是从后往前面填的所以我们要关注最后一个位置当我们救出公主的时候肯定要保证自己的血量不为0所以在[m][n-1]和[m-1][n]位置填1就好其他位置为不影响 状态转移方程应该都初始化为正无穷。 4、 填表顺序
从下往上填写在从右往左。
5、返回值
dp[0][0]
b、代码
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] 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(1, dp[i][j]);}// 返回结果return dp[0][0];}
}; Leetcode 测试结果
