目录
leedcode 62.不同路径
leedcode 63.不同路径!!
leedcode LCR 166.珠宝的最高价值
leedcode 931.下降路径最小和
leedcode 64.最小路径和
leedcode 174.地下城游戏
上一篇文章链接：【算法学习计划】动态规划 -- 斐波那契数列模型
leedcode 62.不同路径
我们在上一篇文章中，已经详细讲过动态规划问题需要的解题步骤了
没看过耶没关系，在这篇文章中，我还会带大家再梳理一遍做动态规划题目时候的步骤
先来看题目：
题意非常简洁明了，就是从左上角走到右下角，一共有多少条路线（每次只能往下或者往右）
那我们是否可以这样做：
开辟一个二维数组，而该数组中的每一个位置就代表：我到达这个位置的时候，一共有多少条路线
如果按照这个方向去想的话，我们要想到达dp[i][j]位置，可以从上方或者从左边过来
而到达上方和左边本身就有一定的路径条数，所以不断累加，最后在dp[m][n]位置（右下角）里面存储的就是我们想要的结果（到达右下角有多少条路径）
而我们的状态表示方程就是 dp[i][j] = dp[i-1][j] + dp[i][j-1]
对于初始化，由于我们是拿的上方和左边的路径条数做加法，那么我们在最上方和最左边就会存在越界问题
为了解决这个越界问题，我们可以在数组大小 方面下手，如下图：
我们可以将dp表往外扩大一圈，而将扩大部分全部填充为0，除了左上角的上面一个位置或者左边一个的位置（因为我们需要保证刚开始出发时的初始值为1，则不会影响后续计算）
代码如下：
class Solution {
public:int uniquePaths(int m, int n) {// 1. 创建dp表vector<vector<int>> dp(m+1, vector<int>(n+1));// 2. 初始化dp[0][1] = 1;// 3. 填表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];// 4. 返回值return dp[m][n];}
};leedcode 63.不同路径!!
我们先来看一看题目：
这一题其实和开始的第一道题差不多，问的也是一共有多少条路径
唯一不同的就是，这里多了一些阻碍，有阻碍的地方不能通行
所以我们大致的思路和上面一道题目差不多，就是在开始主逻辑之前做一个判断，如果该位置有阻碍，就让dp表的这个位置直接为0（代表不能过），然后continue即可
代码如下：
class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& G) {int m = G.size(), n = G[0].size();// m是列，n是行// 1. 创建dp表vector<vector<int>> dp(m+1, vector<int>(n+1));// 2. 初始化dp[0][1] = 1;// 3. 填表for(int i = 1; i <= m; i++)for(int j = 1; j <= n; j++){if(G[i-1][j-1] == 1){dp[i][j] = 0;continue;}dp[i][j] = dp[i-1][j] + dp[i][j-1];}// 4. 返回值return dp[m][n];}
};leedcode LCR 166.珠宝的最高价值
如果上面的题目搞懂了，相信这道题目也不会是问题
这一题的状态表示变成了：到达该位置时（包括自身这个位置），能拿到最高的珠宝价值为多少
而我们的状态表示则有了一点变化，因为我们要包含自己到达的位置本身，所以我们需要在比较出上方和左边的较大值后，再加上自己所在位置的价值本身，所以状态表示方程就变成了：
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + frame[i-1][j-1];（frame为珠宝价值的函数，而因为我们会将dp表扩大一圈防止越界问题，所以dp表和frame数组的下标并不相同，这点需要注意）
我们的dp表依然是构建一个二维数组，初始化则是全部为0即可，这件事情vector本身时默认的，所以我们并不需要做什么
最后返回dp表的最右下角即可
代码如下：
class Solution {
public:int jewelleryValue(vector<vector<int>>& frame) {// m 是列, n 是行int m = frame.size(), n = frame[0].size();// 1.创建dp表vector<vector<int>> dp(m+1, vector<int>(n+1));// 2.初始化// 3.填表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];// 4.返回值return dp[m][n];}
};leedcode 931.下降路径最小和
这道题其实通过上面题目的练习之后，他也没有想象中的那么难了
我们完全可以想到：创建一个dp表，然后dp表中的每一个位置代表的是：到达这个位置之后，最小的和是多少(包括这个位置本身的数)
而由于题目有特殊的条件，也就是只能是往左下，下和右下三个位置中选一个移动一格，所以我们可以额外写一个函数，专门用来判断给过去的三个数中的最小值，如下：
int min_three_num(int a, int b, int c)
{return min(a, min(b, c));
}而我们的状态表示方程即为：
dp[i][j] = min_three_num(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]) + matrix[i-1][j-1];
其中，matrix是题目给的装载每个位置的信息数组
创建dp表依旧是创建一个二维数组
而初始化工作的话，我们可以直接复制matrix数组的第一行，因为有了第一行之后，表的后面才有数可以选择
之后的填表则是从左上到右下依次填即可
返回值这里还有一点可以说，因为我们要的是到达最下面时，和最小的那个数
但是最下面有一整行，所以我们需要在最后一行的所有数中将数拿出来一个个比较找出最小
但是单独做这个步骤会不会有点没必要
因为我们完全可以在外面创建一个变量res，这个变量的值就是INT_MAX，代表int的最大值
而我们在填表的过程中就可以比较了，当遍历到最后一行的时候，我们就可以将计算好的结果和res进行比较，如果比res小，那么res就变成这个数，这样，当我们遍历完之后，也就顺便将最小值挑选出来了
代码如下：
class Solution {
public:int min_three_num(int a, int b, int c){return min(a, min(b, c));}int minFallingPathSum(vector<vector<int>>& matrix) {int n = matrix.size(), res = INT_MAX;// 临界情况处理if(n == 1) return matrix[0][0];// 创建dp表vector<vector<int>> dp(n + 1, vector<int>(n + 2, INT_MAX));// 初始化for(int k = 1; k <= n; k++) dp[1][k] = matrix[0][k-1];// 填表for(int i = 2; i <= n; i++)for(int j = 1; j <= n; j++){dp[i][j] = min_three_num(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]) + matrix[i-1][j-1];if(i == n && dp[i][j] < res)res = dp[i][j];}// 返回值return res;}
};leedcode 64.最小路径和
这道题没什么好说的，和上面的题大差不差，甚至比较简单
dp[i] 代表的就是到达这个位置之后，包括这个位置本身，最小的和是多少
而状态表示方程就是：dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + grid[i-1][j-1];
grid数组是题目给的信息数组
代码如下：
class Solution {
public:int minPathSum(vector<vector<int>>& grid) {// m 是列, n 是行int m = grid.size(), n = grid[0].size();// 1.创建dp表vector<vector<int>> dp(m+1, vector<int>(n+1, INT_MAX));// 2.初始化dp[0][1] = dp[1][0] = 0;// 3.填表for(int i = 1; i <= m; i++)for(int j = 1; j <= n; j++)dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + grid[i-1][j-1];// 4.返回值return dp[m][n]; }
};leedcode 174.地下城游戏
这道题还挺有意思的
我们先来试一试按照以前的逻辑推一遍，建一个dp表，然后dp表中的每一个位置都代表到达这个位置时，骑士需要的最少健康值
但是我们很快会发现，这样子进行不下去，因为如果我们按照这个逻辑去推理的话，需要在每一个位置都保存两个信息，一个是到达的需要的最少健康值，另一个是一路走来的数值的和，因为我们需要比较是否需要对最少健康值进行更改
光是听字面意思，我们就需要建立如下样式的dp表：
vector<vectcor<pair<int, int>>> dp (m, vector<pair<int, int>>(n))，吓死个人
后续的逻辑处理更是头大，而我们完全不需要用这种方式
前面的所有问题都是：我们dp表中的位置代表我们到达这个位置之后巴拉巴拉，都是以这个位置为终点
但是换个方向想呢？如果我们以该位置为起点呢？也就是，我们从这个位置出发，到达终点需要的最少健康值，然后一步步倒推即可
我们倒推回去的话，就只需要记录从每一个位置出发时，最少需要多少健康值，就足够了，而这也正是我们的状态表示
我们从这个位置出发时，可能往右，也可能往下，假设往右，从右边一个位置出发时，我们最少需要7点健康值，而我们当前位置的值为-3，那么我们也就需要7-（-3）点健康值也就是10点健康值，才能从这个位置出发，而往下走的情况也是一样的
而向下走和向右走之间，我们需要选一个最小初始健康值，所以还有一个min的逻辑
由此，我们就能推导出我们的状态表示方程了，即：
dp[i][j] = min(dp[i][j+1] - dungeon[i][j], dp[i+1][j] - dungeon[i][j]) ;
也可以简写成：dp[i][j] = min(dp[i][j+1], dp[i+1][j]) - dungeon[i][j];
但是这里有一个小细节！！！
如果我们遇到的值，是一个超级大的正数呢？那么我们最终相减之后的值就是一个很大的负数
比如往下走最少要7点健康值，现在我这个位置是30，7-30=-23，也就是说我需要-23点健康值就能下地下城救公主了，这显然不符合逻辑
而我们最少需要1点健康值下地下城，所以在最后我们还需要有一个max（1， dp[i][j]）的逻辑
也就是，如果变成负数了，我们就需要将其变成最少1点健康值下地下城
可能有人不是很能理解为什么要有max（1， dp[i][j]）这个逻辑，为什么能直接就是1，我这么说你就懂了：
增益抵消需求：
-
若当前房间的值（增益）足够大（如正数），则即使初始健康值很低（如1），进入该房间后增益可覆盖后续需求。
-
此时，无需为后续路径预留额外健康值，只需保证进入当前房间前的最低存活值（1点）
代码如下：
class Solution {
public:int calculateMinimumHP(vector<vector<int>>& dungeon) {int m = dungeon.size(), n = dungeon[0].size();vector<vector<int>> dp(m+1, vector<int>(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][j+1], dp[i+1][j]) - dungeon[i][j];dp[i][j] = max(1, dp[i][j]);}return dp[0][0];}
};自此，我们今天这篇文章就结束了！！
今天我们学习了动态规划算法中的路径问题，通过这6道题目，相信大家对动态规划的认识又更进一步了
后续博主还会持续更新......谢谢大家
 QT 按键事件)