【算法学习】路径问题-动态规划_动态规划记录路径

前言

        在动态规划中存在一些路径问题很值得深究。比如给出一个二维的表格，到达特定位置时想要表达出的状态是什么，如何通过迭代方程得到的。重点就是将题目的信息转换为动态方程解的过程。

        本篇博客记录一些路径问题的相关动态规划题目，便于后续我的复习与归纳整理。

一、不同路径Ⅱ

题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题目解析：

        题目让我们求出从左上角到右下角存在多少不同的路径，并且是一个二维的表格。可以基本确定是一个动态规划的题目。老规矩，先确定我们想要表示的状态是什么。

        根据经验，我们一般选取dp表中的某位置：以此为结尾，表示.... 或者以此为开头，表示....，这里我们按常规的结尾来。

        根据题目，我们可以确定，以i，j为结尾，表示到达此处有多少条不同的路径。

        那么现在需要分析状态转移方程式。我们需要就近分析，并且结合题目。因为我们状态表示的就是到达此处，题目规定只能向下和向右移动，那么一定是左边或者上面过来的。

        其次，因为网格中存在障碍物，如果此处为障碍物，那么左边和上面都过不来了。

综上，我们可以总结一下到达此处，大的方向两种情况：

        1.此处为障碍物，那么dp值为0.

        2.此处不为障碍物，那么就是左边和上面过来。

根据分类计数原理，可以得到状态转移方程：

        dp[i][j] = g[i][j] == 1 ? 0 : dp[i][j - 1] + dp[i - 1][j];(其中g表示此位置题目给的是否是障碍)

        然后我们需要初始化避免数组越界。因为i-1和j-1的关系，如果我们要正常的初始化，那么就要初始化第一行和第一列，显然很麻烦，代码书写也不简洁，我们利用虚拟节点的方式进行初始化。

如果利用虚拟节点，需要注意下面的两个问题：

1.虚拟节点内的值保证填表的正确性。

2.dp表与题目给我们的表的映射关系。

        这里我们的虚拟节点就是在原本的表格上上面新增了一行，左边新增了一列。所以映射关系是每次遍历-1即可。（1,1->0, 0）

        观察我们需要初始化的第一行和第一列：第一行只能除开第一个外，只能从左边过去，第一列除开第一个外只能从上面下来，所以虚拟节点给0完全没有问题。（保证了状态计算没有问题）

        对于第一个，本身从此处出发，也就一种路径，所以我们需要让此处dp值为1，只需要它上面或者左边的虚拟节点的值为1（只能有一个）即可。

        填表顺序自然是从上到下，从左到右，返回值为dp[m][n]表示打到右下角时不同的路径。

编码： 

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        // 构建dp表
        vector<vector<int>> dp(m + 1, vector<int>(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] == 1) dp[i][j] == 0;
                else dp[i][j] = dp[i - 1][j] + dp[i][ j - 1];
            }
        return dp[m][n];
    }
};

时间复杂度：O(m*n) 

空间复杂度：O(m*n)

二、下降路径最小和

题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题目解析：

        题目想要表达的意思很简单，只是描述的相对复杂一点。

        此题的意思是从第一行的任意位置开始，每次选取以自身坐标为中心，下面的三个坐标，每次选择较小的。最后确定下降到最后一行哪次最小和。

        也就是说最后一行的每个位置的最小和求出进行比较即可。

        本题也是一个典型的动态规划题，我们确定状态就以以当前位置结尾，最小的下降和表示对应的dp值。

        对于状态转移方程，就近分析：想要到达此位置只能是上一行的三个位置才能到达（中间，左边，右边），类似下表：

所以，因为是求最小，那么在上面过来的状态中选取最小即可。

dp[i, j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1]) + m[i][j]; (m[i][j] 为对应下标的具体数值)

        然后我们需要确定初始化防止填表时数组越界。

        可以看到，因为存在i-1、j-1、j+1.所以我们需要初始化第一行、第一列和最后一列。想要不单独初始化还是增加虚拟节点，就在初始化的这一行两列增加一行和两列即可。

        首先确定初始化的值正确，第一行要保证初始值，所以第一行虚拟节点设置为0即可；第一列和最后一列除开第一行下面的数是什么情况？它们需要遵循选择最小的和的方式进行规划了，确保虚拟节点不影响它们就设置为INT_MAX即可。

        填表顺序从上到下即可。返回值返回dp最后一行的最小值即可。

编码： 

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n = matrix.size();
        vector<vector<int>> dp(n + 1, vector<int>(n + 2, INT_MAX));
        for (int i = 0; i < n + 2; ++i) dp[0][i] = 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 = dp[n][0];
        for (int i = 1; i <= n; ++i) ret = ret < dp[n][i] ? ret : dp[n][i];
        return ret;
    }
};

时间复杂度：O(n^2)

空间复杂度：O(n^2) 

三、地下城游戏 

题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题目解析：

        此题在状态确认上需要确定对方向。

        同样的，此题问救到公主的最低健康值，也就是意味着就到公主的最低承伤。

        如果按照我们平时的常规思路：设置dp的状态表示为走到i, j位置结束的最低健康值（最低承伤）可以么？

        注意我们的描述：最低承伤（最低健康值）。它是对应的从起点到此处的结果还是从起点到终点的结果呢？自然是后者，那么这个状态就自然不能描述。

简单举个例子：

        比如迷宫是这样的：-1 -2 -5 8 -1

        走到第3格的时候我们承伤是-8，表示到达第3格的最低健康值应该是9.但是过了第四格，我们发现承受是0？那是不是最低健康值为1就可以了吗？自然不行。

        例子表明，如果是以...结尾的经验来做，是没有考虑到综合的影响的，表示的状态并不正确。（最低承伤可以表示，但是最低健康值不能了，因为存在正数）

        那么我们反其道行之，设置do中的状态表示为以i, j为起点，到终点的最低健康值即可。

        此时为什么正确？因为能够去计算最低健康值了，排除正数带来的影响。

简单举个例子：

        比如迷宫是这样的：-1 -2 -5 8 -1

        从结尾开始往前递进，第五格最低健康为（1 - (-1) 至少一点血）2（承伤是-1），第四格最低健康为2 - 8 = -6，此时小于0了，表示奶过头了，保证最低血量1即可。

        状态对比发现，从此点开始，后状态表示并不冲突，所以可以。

        状态表示明确后，状态转移方程很简单就出来了：

dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - d[i][j]; (d[i][j] 表示此处的减血和增血值)

if dp[i][j] <= 0 : dp[i][j] = 1;

        因为存在i+1和j+1，所以初始化最后一行和最后一列即可，利用虚拟节点，为了保证初始化正确，需要保证dp[m - 1][n - 1](原本是最后一个元素，现在新增了一行一列-最后一列和最后一行)=承伤值得绝对值 + 1即可，那么虚拟节点对应设置为1即可，其他不能对填表造成影响，因为是取最小值，设置为INT_MAX即可。

        填表顺序是从左到右，从下到上，返回值就是dp[0][0];

编码： 

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size(), n = dungeon[0].size();
        // 创建dp表
        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 + 1][j], dp[i][j + 1]) - dungeon[i][j];
                dp[i][j] = max(1, dp[i][j]);
            }
        
        return dp[0][0];
    }
};

时间复杂度：O(m * n)

空间复杂度：O(m * n)