中山专业做网站的公司,手机网站怎么设计,做地方门户网站的排名,天元建设集团有限公司属于什么企业动态规划算法介绍
基本原理和解题步骤
针对于动态规划的题型#xff0c;一般会借助一个 dp 表#xff0c;然后确定这个表中应该填入什么内容#xff0c;最终直接返回表中的某一个位置的元素。
细分可以分为以下几个步骤#xff1a; 创建 dp 表以及确定 dp 表中所要填写位…动态规划算法介绍
基本原理和解题步骤
针对于动态规划的题型一般会借助一个 dp 表然后确定这个表中应该填入什么内容最终直接返回表中的某一个位置的元素。
细分可以分为以下几个步骤 创建 dp 表以及确定 dp 表中所要填写位置的含义这一步关乎到最终推导出的状态转移方程一般是根据题意或者根据以往做题的经验得出的。一般要么是以某一个位置结尾进行分析要么是以某一个位置为开头进行分析。 确定状态转移方程是指针对 dp 表中的某一个单独分析这个位置应该填入什么值。在进行这一步时可以假设确定该位置元素时所需要的所有其他位置的值都已经确定了。 初始化有些题目在创建完 dp 表之后如果直接用状态转移方程填表会导致越界的情况所以要在某些会越界的位置单独进行初始化。 确定填写 dp 表时的填写顺序dp 表并不一定是从前往后填写的因为有可能推导出的状态转移方程中某一个位置中元素的值是跟该位置之后的位置有关的所以填表顺序也应该结合题意和状态转移方程决定。 确定返回值根据题目要求找出应该返回 dp 表中的哪一个值。
例题
力扣 91. 解码方法
创建 dp 表以及确定 dp 表中所要填写位置的含义
这道题中根据解题经验需要以某一个位置为结尾进行分析即 dp[i] 表示在字符串 s 中从开头到 i 位置这段子字符串中一共有多少种解码方法。
确定状态转移方程
这道题的状态转移方程并不是一成不变的需要分情况进行讨论。 所以状态转移方程可以表示为 dp[i] dp[i - 1] dp[i - 2]也就是上述两种情况的和。 初始化
由于推导出的状态转移方程中dp[i] 的计算需要用到前两个位置的值所以在开始填表之前为了防止越界需要先初始化确定 dp[0] 和 dp[1]。
dp[0]第一个元素只能单独解码解码成功为 1解码失败为 0。
dp[1]第二个元素可以单独解码也可以和第一个元素一起解码单独解码成功为 1失败为0单独解码不成功但是和前一个元素一起解码成功为 1失败为0单独解码成功和前一个元素一起解码也成功为 2。
确定填表顺序
由状态转移方程可以看出应该是从前向后填表。
确定返回值
该题目需要返回以最后一个位置为结尾的字符串所有可能的解码总数所以应该返回 dp[n - 1]。
代码
class Solution
{
public:int numDecodings(string s) {// 创建 dp 表int n s.size();vectorint dp(n);// 初始化if (s[0] 0) return 0;dp[0] 1;if (n 1) return dp[0];if (s[1] ! 0) dp[1] 1;int t (s[0] - 0) * 10 (s[1] - 0);if (t 10 t 26) dp[1] 1;// 填表for (int i 2; i n; i) {if (s[i] ! 0) dp[i] dp[i - 1];t (s[i - 1] - 0) * 10 (s[i] - 0);if (t 10 t 26) dp[i] dp[i - 2];}return dp[n - 1];}
};
但是上面的初始化其实看起来有一些繁琐可以通过增加虚拟节点的方式让代码变得更简洁。
说白了就是在状态转移方程会越界的地方增加虚拟节点并确保这个节点中的值不影响真正节点中填入的正确数据。
在这道题中可以在 dp 的最前面增加一个位置并初始化为 1然后就只需要对字符串 s 的第一个字符进行判断从第二个字符开始就可以使用状态转移方程了。
但是注意增加了一个虚拟节点之后使用状态转移方程时要注意字符的下标是否和 dp 表的下标对应。
更改后的代码
class Solution
{
public:int numDecodings(string s) {// 创建 dp 表int n s.size();vectorint dp(n 1);// 初始化dp[0] 1;dp[1] s[1 - 1] ! 0;// 填表for (int i 2; i n; i) {if (s[i - 1] ! 0) dp[i] dp[i - 1];int tmp (s[i - 2] - 0) * 10 (s[i - 1] - 0);if (tmp 10 tmp 26) dp[i] dp[i - 2];}return dp[n];}
};
动态规划中的路径问题
力扣 62. 不同路径
力扣 62. 不同路径
这道题中的路径可以模拟为一个 m 行 n 列的二维数组。
解题步骤
创建 dp 表以及确定 dp 表中所要填写位置的含义
首先根据写题经验先确定出这道题应该使用的解题思路是 “以某一个位置为结尾进行分析”。
其次由于要记录路径中的每一个位置所以这道题的 dp 表应该是一个m 行 n 列的二维数组。
每一个位置的含义也就是 dp[i][j] 指的是从0 0到 ij位置一共有多少种路径。
确定状态转移方程
题目指出每一次移动只能向下或者向右移动所以到达ij位置之前的一个位置一定是i - 1j或者ij - 1。
所以ij位置的路径总数应该是i - 1j和ij - 1两个位置路径总数之和。
所以dp[i][j] dp[i - 1][j] dp[i][j -1]。
初始化
由于第一行和第一列中的元素只能由自己的前一个位置到达所以它们所对应的 dp 表中的值应该是 1。
确定填表顺序
根据状态转移方程可以看出应该从二维数组的左上角到右下角依次填入数据。
确定返回值
题目要求返回到达mn的所有路径总数所以应该返回 dp[m - 1][n - 1]。
代码
class Solution
{
public:int uniquePaths(int m, int n) {// 创建 dp 表vectorvectorint dp(m, vectorint(n, 0));// 初始化for (int i 0; i m; i) dp[i][0] 1;for (int j 0; j n; j) dp[0][j] 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 - 1][n - 1];}
};
力扣 63. 不同路径二
力扣 63. 不同路径二
这道题跟上面的题唯一的不同在于需要注意二维数组中存在障碍物的位置。
原理还是一样的只是如果某一个位置的上边或者左边有障碍物就不应该再加上这条路径。
其他过程不再赘述。
代码
class Solution
{
public:int uniquePathsWithObstacles(vectorvectorint obstacleGrid) {if (obstacleGrid[0][0] 1) return 0;int m obstacleGrid.size(), n obstacleGrid[0].size();if (obstacleGrid[m - 1][n - 1] 1) return 0;// 创建 dp 表vectorvectorint dp(m, vectorint(n, 0));// 初始化for (int i 0; i m; i){if (obstacleGrid[i][0] 0) dp[i][0] 1;else break;} for (int j 0; j n; j){if (obstacleGrid[0][j] 0) dp[0][j] 1;else break;}// 填表for (int i 1; i m; i){for (int j 1; j n; j){// 如果有障碍物, 就不做处理, 保持 0 值if (obstacleGrid[i][j] 0) dp[i][j] dp[i - 1][j] dp[i][j - 1];}}return dp[m - 1][n - 1];}
};
力扣 166. 珠宝的最高价值
力扣 166. 珠宝的最高价值
解题步骤
创建 dp 表以及确定 dp 表中所要填写位置的含义
首先根据写题经验先确定出这道题应该使用的解题思路是 “以某一个位置为结尾进行分析”。
其次由于要记录路径中的每一个位置所以这道题的 dp 表应该是一个m 行 n 列的二维数组。
每一个位置的含义也就是 dp[i][j] 指的是从0 0到 ij可以拿到的珠宝的最高价值之和。
确定状态转移方程
题目指出每一次移动只能向下或者向右移动所以到达ij位置之前的一个位置一定是i - 1j或者ij - 1。
所以ij位置的最大价值应该是i - 1j和ij - 1两个位置中的最大价值和ij位置本身的价值之和。
所以dp[i][j] max(dp[i - 1][j] dp[i][j -1]) frame[i][j]。
初始化
由于第一行和第一列中的元素只能由自己的前一个位置到达所以它们所对应的 dp 表中的值应该是本身的价值加上前一个位置的最大价值。
确定填表顺序
根据状态转移方程可以看出应该从二维数组的左上角到右下角依次填入数据。
确定返回值
题目要求返回到达右下角时能拿到的珠宝的最大价值所以应该返回 dp[m - 1][n - 1]。
代码
class Solution
{
public:int jewelleryValue(vectorvectorint frame) {// 创建 dp 表int m frame.size(), n frame[0].size();vectorvectorint dp(m, vectorint(n, 0));// 初始化dp[0][0] frame[0][0];for (int i 1; i m; i) dp[i][0] dp[i - 1][0] frame[i][0];for (int j 1; j n; j) dp[0][j] dp[0][j - 1] frame[0][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]) frame[i][j];}}return dp[m - 1][n - 1];}
};
力扣 931. 下降路径最小和
力扣 931. 下降路径最小和
解题步骤
创建 dp 表以及确定 dp 表中所要填写位置的含义
首先根据写题经验先确定出这道题应该使用的解题思路是 “以某一个位置为结尾进行分析”。
其次这道题目的 “结尾” 指的是最后一行而不是右下角。
dp[i][j] 指的是 从第一行到ij位置路径上所有点相加的最小值。
确定状态转移方程
由题目可得到达ij位置之前的一个位置一定是i - 1j或者i - 1j - 1或者i - 1j 1。
所以ij位置的最小路径和应该是i - 1ji - 1j - 1以及i - 1j 1三个位置中的最小值和ij位置本身的值相加
所以dp[i][j] min(dp[i - 1][j], min(dp[i - 1][j -1], dp[i - 1][j 1])) matrix[i][j]。
初始化
这道题可以直接用 matrix 二维数组来初始化 dp 表后续可以直接在此基础上更改。
确定填表顺序
根据状态转移方程可以看出应该从上往下每一行依次填入数据。
确定返回值
题目要求返回到达最后一行的路径上和的最小值所以应该返回 dp 表中最后一行中的最小值。
代码
class Solution
{
public:int minFallingPathSum(vectorvectorint matrix) {// 创建 dp 表 初始化vectorvectorint dp(matrix);// 填表int n matrix.size();for (int i 1; i n; i){for (int j 0; j n; j){if (j 0)dp[i][j] min(dp[i - 1][0], dp[i - 1][1]);else if (j n-1)dp[i][j] min(dp[i - 1][n - 1], dp[i - 1][n - 2]);else{int Min min(dp[i - 1][j - 1], dp[i - 1][j]);dp[i][j] min(Min, dp[i - 1][j 1]);}}}int min dp[n - 1][0];for (int i 1; i n; i)min dp[n - 1][i] min ? dp[n - 1][i] : min;return min;}
};
力扣 64. 最小路径和
力扣 64. 最小路径和
解题步骤
创建 dp 表以及确定 dp 表中所要填写位置的含义
首先根据写题经验先确定出这道题应该使用的解题思路是 “以某一个位置为结尾进行分析”。
其次由于要记录路径中的每一个位置所以这道题的 dp 表应该是一个m 行 n 列的二维数组。
每一个位置的含义也就是 dp[i][j] 指的是从0 0到 ij所有路径中的最小和。
确定状态转移方程
题目指出每一次移动只能向下或者向右移动所以到达ij位置之前的一个位置一定是i - 1j或者ij - 1。
所以ij位置的最小路径和应该是i - 1j和ij - 1两个位置中的最小值和ij位置本身的值之和。
所以dp[i][j] min(dp[i - 1][j] , dp[i][j -1]) grid[i][j]。
初始化
这道题可以按照先开一个二维数组再初始化第一行和第一列的方法初始化。
但是也可以直接用题目给出的原数组初始化虽然后续还是要对第一行和第一列进行改动。
各位看自己心情选择吧。
确定填表顺序
根据状态转移方程可以看出应该从二维数组的左上角到右下角依次填入数据。
确定返回值
题目要求返回到达右下角的所有路径和中的最小值所以应该返回 dp[m - 1][n - 1]。
代码
class Solution
{
public:int minPathSum(vectorvectorint grid) {// 创建 dp 表int m grid.size(), n grid[0].size();vectorvectorint dp(grid);// 初始化for (int i 1; i m; i) dp[i][0] dp[i - 1][0];for (int j 1; j n; j) dp[0][j] dp[0][j - 1];// 填表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]);}}return dp[m - 1][n - 1];}
};
力扣 174. 地下城游戏
力扣 174. 地下城游戏
这道题就有点不一样了它不能用 “以某一个位置为结尾进行分析”。
解题步骤
创建 dp 表以及确定 dp 表中所要填写位置的含义
如果还是以某一个位置为结尾进行分析则 dp[i][j] 表示从七点到达ij位置所需的最低健康点数这时虽然知道了 dp[i -1][j] 和 dp[i][j - 1]但是就算可以保证骑士可以到达ij但是能不能到达最后还受后面数字的影响所以这个方法行不通。
如果以某一个位置为起点进行分析则 dp[i][j] 表示骑士从ij位置到最后所需的最低健康点数这时可以从右下角开始。
确定状态转移方程
dp[i][j] 表示从 i, j 位置出发到达终点所需的最小的健康点数
往右边走则该位置的健康点数减去该位置消耗的健康点数应该大于等于右边位置所需的健康点数
dp[i][j] dungeon[i][j] dp[i][j 1] - dp[i][j] dp[i][j 1] - dungeon[i][j]
往下边走则该位置的健康点数减去该位置消耗的健康点数应该大于等于下边位置所需的健康点数
dp[i][j] dungeon[i][j] dp[i 1][j] - dp[i][j] dp[i 1][j] - dungeon[i][j]
所以dp[i][j] min(dp[i 1][j], dp[i][j 1]) - dungeon[i][j]
初始化
这道题我用的方法是先开一个二维数组然后初始化最后一行和最后一列。
当然如果你有更喜欢的方法也可以。
各位看自己心情选择吧。
确定填表顺序
根据状态转移方程可以看出应该从二维数组的右下角到左上角依次填入数据。
确定返回值
题目要求求出从起点能顺利到达右下角所需的最低健康点数所以应该返回 dp[0][0]。
还有一个需要注意的点由状态转移方程可以看出一个漏洞如果dungeon[i][j]的值是一个很大的正数则会导致dp[i][j] 0表明骑士已经死亡 所以当dp[i][j]为负数时应将其变为1 dp[i][j] max(1, dp[i][j])。
代码
class Solution
{
public:int calculateMinimumHP(vectorvectorint dungeon) {// 创建 dp 表int m dungeon.size(), n dungeon[0].size();vectorvectorint dp(m, vectorint(n));// 初始化dp[m - 1][n - 1] 1 - dungeon[m - 1][n - 1];dp[m - 1][n - 1] max(1, dp[m - 1][n - 1]);for (int i m - 2; i 0; i--){dp[i][n - 1] dp[i 1][n - 1] - dungeon[i][n - 1];dp[i][n - 1] max(1, dp[i][n - 1]);}for (int j n - 2; j 0; j--){dp[m - 1][j] dp[m - 1][j 1] - dungeon[m - 1][j];dp[m - 1][j] max(1, dp[m - 1][j]);}// 填表for (int i m - 2; i 0; i--){for (int j n - 2; 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];}
};
总结
在我看来动规问题中的路径问题应该有以下几点值得注意的 开出来的 dp 表中每一个位置到底代表什么。 填表的时候一定要注意在容易越界的地方进行合适的初始化初始化的数据一定不能影响后面数据的正确性。 到底该 “以某一个位置为结尾” 还是 “以某一个位置为起点” 应该看 dp 表中的某一个位置的值是否还受后面的值的影响。
