解锁动态规划的奥秘：从零到精通的创新思维解析（5）

解锁动态规划的奥秘：从零到精通的创新思维解析（5）

前言：

小编在前几日分享了关于动态规划的题目，今天我们继续沿着之前的思路，深入探索动态规划的魅力。今天要讲解的依旧是路径问题，与前面讲过的题目在解法上有一定相似之处。如果大家对这类题目的解法还不太熟悉，可以回顾一下之前的文章，巩固基础。话不多说，让我们进入今天的代码之旅！

正文：

1.最小路径和

1.1.题目来源

本题同样来自于力扣，下面小编给出它的链接：64. 最小路径和 - 力扣（LeetCode）

1.2.题目解读

本题读起来还是很简单的，此时就是给定我们一个数组，每个位置上都有一个数组，询问当我们走到最后位置的时候的所有路径中，寻找路径上的数加起来最小的那条路径，这个题目其实就是小编之前讲述的珠宝问题，只不过珠宝问题是求解最大珠宝，这个问题是求解最小路径和罢了，下面我们直接进行思路讲解。

1.3.思路讲解

对于动态规划的题目，还是要先创建一个dp表，此时根据题目我们可以知晓需要用到一个二维的dp表，此时创建完dp表以后，就可以五步走分析这个题目了。

1.状态表示

对于线性的dp表，我们通常都是经验 + 题目要求来进行状态表示的，此时我们可以某个位置为结尾或者进行分析，本题的状态表示也是很容易看出的，dp[i] [j]可以表示为到达[i，j]位置时的最小路径和，根据此时的状态表示，我们就可以书写出状态转换方程。

2.状态转换方程

此时这个方程可以通过题目的解读来分析出来，我们知道，此时到达[i，j]位置的方式无非就是两种，分别是从上面到达，或者从左边到达，此时我们计算他俩之间的最小值，再加上当前位置本身的值，来推测出状态转换方程，其分析过程如下所示：

方程具体书写形式如下所示：

dp[i][j] = min(dp[i - 1][j],dp[i][j - 1]) + nums[i][j];

3.初始化

本题的初始化难度也是不大的，我们通过方程，就可以知道可能第一行或者第一列会有越界的风险，所以本题目最好的做法就是多开辟一行一列当做虚拟节点，此时虚拟节点的值我们要通过对于题目的分析和方程的拆解才可以获取，此时不难看出，我们需要求取最小值，所以最好的方式就是在我们创建dp表的时候，让dp表每一个位置的值为int类型的最大值，此时我们就不会担心虚拟节点影响我们后续的填表了，当然，仅仅这样初始化是不可以的，我们可以看一看原数组第一个位置的值，此时它如果带入方程时，需要用到头顶和左边的数据，所以如果他们放任不管的话，这个位置的值会变为最大值，可能我这么说各位读者朋友会听不懂，所以我同样画图来给各位解释：

虽然我画的这个图比较抽象，但是我认为它很好的展示了原数组第一个位置的填表时遇到的情况，我们需要让它周围的值变为0，不然的话会出现它为无穷大的情况，这算是一个小小的特例了。

4.填表顺序

从上到下，从左到右。

5.返回值

根据题目的解读，此时我们返回最后一个位置即可。

1.4.代码讲解

此时我们需要先创立一个dp表，此时在创建的时候记得多开辟一行一列，以免出现越界的情况，之后我们对相应的位置进行初始化即可，具体可以看上面小编讲述的初始化。

int m = grid.size(),n = grid[0].size();
vector<vector<int>>dp(m + 1,vector<int>(n + 1,INT_MAX));
dp[0][1] = dp[1][0] = 0;

之后我们根据状态转换方程进行循环填表即可，填表时要注意循环的起始以及下标的映射，因为dp表要比grid多一行一列，所以我们使用grid值的时候，一定要记得对应位置-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]) + grid[i - 1][j - 1];
        }
    }
return dp[m][n];

1.5.完整代码展示

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(),n = grid[0].size();
        vector<vector<int>>dp(m + 1,vector<int>(n + 1,INT_MAX));
        dp[0][1] = dp[1][0] = 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];
    }
};

2.地下城游戏

2.1.题目来源

本题同样来自于力扣，下面小编给出链接：174. 地下城游戏 - 力扣（LeetCode）

2.2.题目解析

这个题目是小编讲述动态规划以来遇到的第一个困难题，当然小编还是那句话，不要被题目难度打败，困难题我们迟早要面对，早面对早克服，那么我们就可以领先别人一大截，废话不多说，小编对这个题目简单的总结一下，本题就是一个骑士要救一个公主，此时公主在右下角的房间，我们需要从左上角走到右下角（上面那个题目大体框架也是这样的），此时骑士是有血量的，我们每到达一个房间的时候，会面对三个情况：1.房间有怪，扣血；2.房间是空的；3.房间有血包，可以回血；此时我们需要计算当我们从左上角到达右下角的时候所需要的最低血量，题目就是讲述了这个情况，下面小编讲述一下这个题目的思路分析。

2.3.思路分析

对于动态规划的题目，我们通常是先创建一个dp表，根据题目，我们可以创建一个二维的dp表，然后五步走即可。

1.状态表示

对于线性dp表，我们通常是根据经验 + 题目分析来做题，此时我们可以选择以某个位置为结尾或者开头来解决题目，此时本题小编选择的是以某个位置为开头来分析问题，所以此时的dp[i] [j]可以表示为以[i，j]位置到重点所需要的最低血量，我们根据这个状态表示可以分析出方程。

2.状态转换方程

此时我们可以通过题目的分析来得到此时的方程，此时我们可以选择往右边走或者往下边走，这就分两种情况进行问题的讨论了，此时我们选取其中的最小值再减去当前位置的值即可，如下图所示：

方程可以写成下面这样：

dp[i][j] = min(dp[i][j + 1],dp[i + 1][j]) - dungon[i][j];

3.初始化

此时本题目的初始化也是很容易看出来的，此时当我们处于最后一个位置的时候，会出现数组越界的情况，此时我们需要多开辟一行，一列作为最后一行最后一列，为了避免虚拟节点的值影响表的正确性，所以我们根据方程可以推断出此时的虚拟节点可以是int的最大值，此时我们找最小值的时候肯定找不到它们，只不过有两个位置需要额外的初始化，它就是数组最后一个位置的右边和下边，此时我们需要用到这两个位置的值的最小值，所以为了避免题目出错，此时我们需要让其值为1即可，这样不会影响结果。

4.填表顺序

因为本题用到了后面元素的值，所以我们要从下往上，从左往右填表。

5.返回值

此时我们返回第一个位置的值即可。

2.4.代码讲解

此时我们需要先创立一个dp表，并且根据初始化的规则进行表的初始赋值操作，此时就是根据小编上面说的初始化规则进行初始化操作即可。

int m = dungeon.size(),n = dungeon[0].size();//m表示行，n表示列
vector<vector<int>> dp(m + 1,vector<int>(n + 1,INT_MAX));
dp[m-1][n] = dp[m][n - 1] = 1;

之后我们就要进行填表了，不过此时的填表我们需要注意一种情况，那就是当前的dp值是否小于1，如果小于1的话，那么此时可能就是后面的血包很大，导致此时无须正数就可以走到，这样肯定是不可以的，初始血量肯定要是正的，所以此时我们让当前的dp值和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];

2.5.完整代码展示

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size(),n = dungeon[0].size();//m表示行，n表示列
        vector<vector<int>> dp(m + 1,vector<int>(n + 1,INT_MAX));
        dp[m-1][n] = 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][j+1],dp[i+1][j]) - dungeon[i][j];
                dp[i][j] = max(1,dp[i][j]);  //避免出现血包过大的情况
            }
        }
        return dp[0][0];
    }
};

3.总结

本文到这里也就完全结束了，请各位读者朋友一定要好好的理解好这两个题目，动态规划的路径问题到这里也就结束了，希望各位可以通过我讲述的题目可以大致掌握这种题目的做法，其实五步走就可以完成大部分动态规划的题，在之后小编题目的讲解中读者朋友应该就会体会到这句话的意义，如果文章有错误的话，可以在评论区点出，我会及时改正，学习的时光总是短暂的，那么各位大佬们，我们下一篇文章见啦！