对于一些二维 DP（例如背包、最长公共子序列），如果把 DP 矩阵画出来，其实状态转移可以视作在网格图上的移动。所以在学习相对更抽象的二维 DP 之前，做一些形象的网格图 DP 会让后续的学习更轻松（比如 0-1 背包的空间优化写法为什么要倒序遍历）。

例题

滑雪

901. 滑雪 - AcWing题库

状态表示：

f[i, j]，所有从(i,j)开始滑的路径的最大长度。

状态计算：

可以从f[i, j]滑任意四个方向（前提是(i, j)比该方向的点高）：

• 向上滑：f[i, j] = f[i + 1, j] + 1。
• 向右滑：f[i, j] = f[i, j + 1] + 1。
• 向下滑：f[i, j] = f[i - 1, j] + 1。
• 向左滑：f[i, j] = f[i, j + 1] + 1。

那最终f[i, j] = max(四个情况) + 1。此外，这道题不会出现环状路径，因此可以用dp，这里用记忆化搜索写：

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 310;

int n, m;
int g[N][N];
int f[N][N];

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int dp(int x, int y)
{
    int &v = f[x][y];
    if (v != -1) return v;

    v = 1;
    for (int i = 0; i < 4; i ++ )
    {
        int a = x + dx[i], b = y + dy[i];
        if (a >= 1 && a <= n && b >= 1 && b <= m && g[x][y] > g[a][b])
            v = max(v, dp(a, b) + 1);
    }

    return v;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            scanf("%d", &g[i][j]);

    memset(f, -1, sizeof f);

    int res = 0;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            res = max(res, dp(i, j));

    printf("%d\n", res);

    return 0;
}

练习题

基础

LCR 166. 珠宝的最高价值 - 力扣（LeetCode）

状态表示：

f[i + 1, j + 1]表示在frame[i + 1][j + 1]时拿到的最大价值，零起点最好写成这样。

状态计算：

• f[i, j + 1]往下走得到f[i + 1, j + 1]，有f[i + 1, j + 1] = f[i, j + 1] + frame[i][j]。
• f[i + 1, j]往右走得到f[i + 1, j + 1]，有f[i + 1, j + 1] = f[i + 1, j] + frame[i][j]。

综上f[i + 1, j + 1]要取它们的最大值。

参考代码如下：

int jewelleryValue(vector<vector<int>>& frame) {
    int n = frame.size(), m = frame[0].size();
    vector<vector<int>> dp(n + 5, vector<int>(m + 5, 0));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]) + frame[i][j];
    return dp[n][m];
}

62. 不同路径 - 力扣（LeetCode）

状态表示：

f[i, j]表示走到[i, j]的总方案数量。

状态计算：

• f[i - 1, j]往下走得到f[i, j]。
• f[i, j - 1]往右走得到f[i, j]。

那么f[i, j]就是这俩方案数的总和。

参考代码如下：

int uniquePaths(int m, int n) {
    vector<vector<int>> f(m + 5, vector<int>(n + 5, 0));
    f[1][1] = 1;
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            f[i][j] += f[i - 1][j] + f[i][j - 1];
    return f[m][n];
}

63. 不同路径 II - 力扣（LeetCode）

在上一题的基础上增加了障碍物，因此要进行判断，如果[i, j]是障碍物，

参考代码如下：

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    int m = obstacleGrid.size(), n = obstacleGrid[0].size();
    vector<vector<int>> f(m + 1, vector<int>(n + 1, 0));
    f[1][1] = obstacleGrid[0][0] != 1;
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            if (obstacleGrid[i - 1][j - 1] == 0)
                f[i][j] += f[i - 1][j] + f[i][j - 1];
    return f[m][n];
}

64. 最小路径和
120. 三角形最小路径和
931. 下降路径最小和 1573
2684. 矩阵中移动的最大次数 1626
2304. 网格中的最小路径代价 1658
1289. 下降路径最小和 II 1697

进阶

1594. 矩阵的最大非负积 - 力扣（LeetCode）

状态表示：

maxVal[i, j]表示从[0, 0]到[i, j]的所有路径的乘积结果，我们要最大值。

minVal[i, j]表示从[0, 0]到[i, j]的所有路径的乘积结果，我们要最小值。

状态计算：

以计算maxVal[i, j]为例，maxVal[i, j]可由如下项一步得到：

• maxVal[i, j] = max(maxVal[i - 1, j] * grid[i][j], minVal[i - 1, j] * grid[i][j])；
• maxVal[i, j] = max(maxVal[i, j - 1] * grid[i][j], minVal[i, j - 1] * grid[i][j]) ；

我们要取它俩的最大值。

为了简化代码，我们将最大值和最小值存成pair，参考代码如下：

const int MOD = 1e9 + 7;
using PLL = pair<long long, long long>;
int maxProductPath(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector<vector<PLL>> dp(m, vector<PLL>(n));
    dp[0][0] = {grid[0][0], grid[0][0]};
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j) {
            if (!i && j)
                dp[i][j] = minmax({dp[i][j - 1].first * grid[i][j],
                                   dp[i][j - 1].second * grid[i][j]});
            else if (!j && i)
                dp[i][j] = minmax({dp[i - 1][j].first * grid[i][j],
                                   dp[i - 1][j].second * grid[i][j]});
            else if (i && j)
                dp[i][j] = minmax({dp[i - 1][j].first * grid[i][j],
                                   dp[i - 1][j].second * grid[i][j],
                                   dp[i][j - 1].first * grid[i][j],
                                   dp[i][j - 1].second * grid[i][j]});
        };

    long long ans = dp[m - 1][n - 1].second;
    return ans >= 0 ? ans % MOD : -1;
}

非常坏0起点，使我讨论一堆情况。

1301. 最大得分的路径数目 1853
2435. 矩阵中和能被 K 整除的路径 1952
174. 地下城游戏
329. 矩阵中的最长递增路径
2328. 网格图中递增路径的数目 2001
2267. 检查是否有合法括号字符串路径 2085
1937. 扣分后的最大得分 2106
1463. 摘樱桃 II
741. 摘樱桃
2510. 检查是否有路径经过相同数量的 0 和 1（会员题）