动态规划2：不同路径模型

2401_87750511

418人浏览 · 2026-05-10 14:10:38

2401_87750511 · 2026-05-10 14:10:38 发布

不同路径

1、不同路径
2、不同路径Ⅱ
3、珠宝的最大价值
4、下降路径最小和
5、最小路径和
6、地下城游戏

1、不同路径

不同路径

状态表示

在这里插入图片描述
分析题目，我们很容易能想到使用二维数组。

我们以到达某一位置有多少条路径为状态表示方法，即：

dp[i][j]表示到达第i行，第j列位置有多少条路径。

状态转移方程

题目要求机器人只能向下，或者向右走一步，所以走到(i, j)位置，可以是从(i-1, j)向下走一步得来，也可以是(i, j-1)向右走一步得来。

从(i-1, j)得来这个角度，就是将从起点到(i-1, j)的每一个方法，与(i-1, j)到(i, j)的一步搭配，方法数为dp[i-1][j]。

同理，从(i, j-1)得来这个角度，就是将从起点到(i, j-1)的每一个方法，与(i, j-1)到(i, j)的一步搭配，方法数为dp[i][j-1]。

所以状态转移方程：

dp[i][j] = dp[i-1][j] + dp[i][j-1];

初始化

考虑到越界的问题，我们要初始化的有第一行和第一列：

在这里插入图片描述
由于从起点到起点，只有一种方法：不动；从起点到第一行或第一列的任何一个位置，只有一种方法：一直向右或一直向下。

所以，第一行和第一列所有值全部初始化成1。

我们不妨多加一行一列，只在一个地方给1，其余都给0：

在这里插入图片描述
这样，我们通过状态转移方程，就可以将实际的第一行和第一列所有值全部初始化成1。

填表顺序

从上到下，从左往右。

返回值

返回dp[m][n]。

代码演示：

class Solution {
public:
    int uniquePaths(int m, int n) {
        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)
            {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }

        return dp[m][n];
    }
};

2、不同路径Ⅱ

不同路径Ⅱ

这道题的解法与“不同路径”非常相似，只是在状态转移方程步骤中加一步判断：

走到(i, j)位置，可以是从(i-1, j)向下走一步得来，也可以是(i, j-1)向右走一步得来：

如果(i, j)位置上有障碍，那么到不了(i, j)位置，方法数为0（不做处理）
如果(i-1, j)或(i, j-1)有障碍，我们不需要另外讨论，因为计算dp[i-1][j]或dp[i][j-1]时，由于障碍，dp[i-1][j]或dp[i][j-1]的值为0

在这里插入图片描述

代码演示：

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

        return dp[m][n];
    }
};

3、珠宝的最大价值

珠宝的最大价值

在这里插入图片描述
这道题，与不同路径也是非常相似。

状态表示

dp[i][j]表示到达(i, j)位置时，拿到所有珠宝的价值总和的最大值。

状态转移方程

(i, j)位置，可以从(i-1, j)位置向下走一步，也可以从(i, j-1)向右走一步：

从(i-1, j)向下走一步，价值总和为(i-1, j)位置处能拿到的最大价值，加上(i, j)位置上的价值
从(i, j-1)向下走一步，价值总和为(i, j-1)位置处能拿到的最大价值，加上(i, j)位置上的价值

然后对求得的两个价值取最大：

dp[i][j] = max(dp[i-1][j] + frame[i-1][j-1], dp[i][j-1] + frame[i-1][j-1]);
// 1.由于我们创建dp数组时，多加了一行和一列，以防止越界情况发生，所以frame要与dp正确对应
// 2.frame[i-1][j-1]是一样的，所以我们可以提取出来
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + frame[i-1][j-1];

初始化

创建dp数组时，多加一行和一列，以防止越界情况发生。

第一行和第一列，可以理解为其左、上方没有珠宝，全部初始化成0。

填表顺序

从上到下，从左到右。

返回值

返回dp[m][n]。

代码演示：

class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) {
        int m = frame.size(), n = frame[0].size();
        vector<vector<int>> dp(m+1, vector<int>(n+1));

        for (int i = 1; i <= m; ++i)
            for (int j = 1; j <= n; ++j)//                 价值数组要与dp数组对应！！！
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + frame[i-1][j-1];

        return dp[m][n]; 
    }
};

4、下降路径最小和

下降路径最小和

在这里插入图片描述

状态表示：

dp[i][j]：到达(i, j)位置时，下降路径的最小和。

状态转移方程

每一个位置都是从这三个位置得来的：

在这里插入图片描述
所以(i, j)位置的最小和，是由(i-1, j-1), (i-1, j), (i-1, j+1)三个位置的最小和的最小值，加上(i, j)位置对应matrix的位置值（matrix[i-1][j-1]）的和：
$d p [i] [j] = min (d p [i - 1] [j - 1], d p [i - 1] [j], d p [i - 1] [j + 1]) + ma t r i x [i - 1] [j - 1]$

初始化

观察状态转移方程，我们可以发现，如果开辟一个空间排布与matrix数组一样的二维数组，那么第一行、第一列、最后一列会越界：

在这里插入图片描述

所以我们加上一列，再加上两行：

在这里插入图片描述
对于新增空间，第一行全初始化成0是可以的，因为matrix第一行的每个位置，下降路径的最小和都是这个位置上的数：

在这里插入图片描述
对于左右两列，则应该设置成整型的最大值。

因为我们不期望新增的最左、最右两列的数参与和的计算算。

所以我们设置左右两列的值为INT_MAX，而不是0。这样比小时，左右两列的INT_MAX就不会被选上：

在这里插入图片描述

填表顺序

从上到下，从左到右。

返回值

这里我们的最小和并不一定是在右下角，而可能是在最后一行的某一位置，所以我们要遍历查找。

代码演示：

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int m = matrix.size();
        // 创建dp表
        // 1.多加一行两列
        // 2.全部初始化成INT_MAX
        // 3.第一行初始化成0
        vector<vector<int>> dp(m+1, vector<int>(m+2, INT_MAX));
        for (int i = 0; i <= m+1; ++i)
        {
            dp[0][i] = 0;
        }

        for (int i = 1; i <= m; ++i)
        {
            for (int j = 1; j <= m; ++j)
            {// 比最小，既可以传两个数，也可以传initializer_list
             // 但是前者效率可能更高
                //dp[i][j] = matrix[i-1][j-1] + min({dp[i-1][j], dp[i-1][j-1], dp[i-1][j+1]});
                dp[i][j] = matrix[i-1][j-1] + min(dp[i-1][j], min(dp[i-1][j-1], dp[i-1][j+1]));
            }
        }

        int min_n = INT_MAX;
        for (int i = 1; i <= m; ++i)
        {// 比大小的新思路
         // 这种不用if的方法，效率可能更高
            //if (min_n > dp[m][i])
            //    min_n = dp[m][i];
            min_n = min(min_n, dp[m][i]);
        }

        return min_n;
    }
};

5、最小路径和

最小路径和

在这里插入图片描述

我们还是先建立一个二维数组，与grid一样（之后会加行、列）。

状态表示

经验 + 题目要求：

dp[i][j]：从左上角开始，到达(i, j)位置时，路径的最小和。

状态转移方程

题目要求每次只能向下或向右移动一步。所以(i, j)位置的路径的最小和，是由这两个位置得来的：

在这里插入图片描述
那么(i, j)位置的dp值，就可以分成两种情况：

在这里插入图片描述

那么我们能很快地想出一个递推式：
$d p [i] [j] = g r i d [i - 1] [j - 1] + min (d p [i] [j - 1], d p [i - 1] [j])$

初始化

初始化要注意两点：

当前位置的dp值，必须由前一步的dp值正确得出。
避免越界。

对于当前的grid网格，我们的做法是多加一行、多加一列。

在这里插入图片描述
那么，我们向多加的网格放入什么初始值呢？0？

不对。我们对于当前位置的上面、左边的dp值，需要比小。而grid网格的值都是非负值。意味着如果向多加的网格放入0，那么0就有可能参与计算，但这是我们不希望的。

所以我们放入整型的最大值：INT_MAX。

在这里插入图片描述

然后将新网格对应网格的(0, 0)位置的上面，或者左边，初始化成0，以确保左上角的dp值正确：

在这里插入图片描述

代码演示：

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[1][0] = 0;

        for (int i = 1; i <= m; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                dp[i][j] = grid[i-1][j-1] + min(dp[i-1][j], dp[i][j-1]);
            }
        }

        return dp[m][n];
    }
};

6、地下城游戏

地下城游戏

在这里插入图片描述
骑士需要从左上角的房间开始，一直到右下角的房间拯救公主。

骑士只能向右或向下。骑士会遇到三种房间：

数值为负的房间：有恶魔守卫，骑士会减少对应数值的血量
数值为0的房间：什么也没有，相当于通道
数值为正的房间：有魔法球，骑士会回复对应数值的的血量

本题要返回骑士能到达最下角所需的最小血量。

状态表示

如果我们定义状态表示为：
dp[i][j]：骑士从左上角到达(i, j)位置，所需的最小血量。

我们很容易就会想成，dp[i][j]会受其上方和左方的影响：

在这里插入图片描述
但是这样想，有问题：

对于题目给出的示例1，假设骑士的最低血量为3，对于第一个房间(0, 0)，能通过；而对于其右边的房间(0, 1)，与下面的房间(1, 0)，骑士都不能通过：

在这里插入图片描述
这时，骑士的最低血量就必须修改为6，也就意味着，dp[i][j]不仅会受其上方和左方的影响，还会受其下方和左方的影响：

在这里插入图片描述
这样就无法进行动态规划了，因为当前位置的右边位置，和下边位置，还没有初始化。

我们不妨换一换思路。

状态表示（新）

dp[i][j]：骑士从(i, j)位置开始直到右下角，所需的最小血量。

状态转移方程

此时骑士的血量，就只受右边位置，和下边位置的影响：

在这里插入图片描述
我们很可能就会直接想出这样一个状态转移方程：
$d p [i] [j] = min (d p [i] [j + 1], d p [i + 1] [j]) - d u n g eo n [i] [j]$

但是，如果dungeon[i][j]是一个可以回复很多血量的魔法球，即dungeon[i][j]是一个很大的正值，意味着骑士在(i, j)位置的最低血量就变为了负值。

骑士的血量最小必须是1，所以我们要拿1，与分情况算出的最小血量比谁大：
$d p [i] [j] = ma x (1, min (d p [i] [j + 1], d p [i + 1] [j]) - d u n g eo n [i] [j])$

初始化

由于我们分不同路径讨论时是比谁小，所以我们将dp数组用INT_MAX初始化。

我们在末尾多加一行、多加一列，以防止越界：

在这里插入图片描述
骑士来到右下角，血量最小必须是1，所以(m-1, n)和(m, n-1)初始化成1，只要一个地方初始化就行。

在这里插入图片描述

填表顺序

从下往上，从右往左

返回值

返回dp[0][0]。

代码演示：

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] = 1;

        for (int i = m-1; i >= 0; --i)
            for (int j = n-1; j >= 0; --j)
                dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1])-dungeon[i][j]);

        return dp[0][0];
    }
};