动态规划入门必学之走方格问题

这篇文章介绍了动态规划入门必学之走方格问题，分享给大家做个参考，收藏极客资料网收获更多编程知识

很多人第一次接触动态规划，都是从“走格子”开始的：在一个二维网格上，从起点走到终点，每次只能做有限几种移动，问方案数、最小代价，或者最大收益。

第一题：最小路径和

给定一个 \(n \times m\) 的非负整数网格 \(a\)，从左上角出发走到右下角，每次只能向右或向下走一步，路径上的数字都要累加。求最小路径和。

例如下面这个 \(3 \times 3\) 的网格：

一种最优路径是：\( 1 \to 3 \to 1 \to 1 \to 1 \)。所以答案是 \( 1 + 3 + 1 + 1 + 1 = 7 \)

如果我们已经知道到达前面格子的最小代价，那么到达当前格子的最小代价，也就能顺手推出来。

设 \( dp[i][j] \) 表示从起点走到格子 \((i,j)\) 的最小路径和。由于每次只能向右或向下，所以到达 \((i,j)\) 的最后一步只可能来自：

• 上方的 \((i-1,j)\)
• 左侧的 \((i,j-1)\)

因此有转移方程：\( dp[i][j] = \min(dp[i-1][j],\ dp[i][j-1]) + a[i][j] \)

这就是 DP 的核心：当前状态来自有限个前驱状态。

初始化

起点最简单：

第一行只能一直从左边走来，因此：

第一列只能一直从上边走来，因此：

遍历顺序

因为 \(dp[i][j]\) 依赖上方和左方，所以自然按从上到下、从左到右的顺序填表。

int main() {
    vector<vector<int>> a = {
        {1, 3, 1},
        {1, 5, 1},
        {4, 2, 1}
    };

    int n = a.size(), m = a[0].size();
    vector<vector<int>> dp(n, vector<int>(m, 0));

    dp[0][0] = a[0][0];

    for (int i = 1; i < n; i++) dp[i][0] = dp[i - 1][0] + a[i][0];
    for (int j = 1; j < m; j++) dp[0][j] = dp[0][j - 1] + a[0][j];

    for (int i = 1; i < n; i++) 
        for (int j = 1; j < m; j++) 
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + a[i][j];
    cout << dp[n - 1][m - 1] << "\n";
}

复杂度

显然时间复杂度是 \( O(nm) \)，空间复杂度也是 \( O(nm) \)

空间优化

上一题的情境下，空间复杂度可以更低。

仔细观察转移式：\( dp[i][j] = \min(dp[i-1][j],\ dp[i][j-1]) + a[i][j] \)。如果我们是一行一行计算，那么在处理第 \(i\) 行时：

• \(dp[i-1][j]\) 是“上一行同一列”
• \(dp[i][j-1]\) 是“当前行左边”

换句话说，计算当前行时，我们并不需要保存整个二维表，只需要保存：

• 上一行的信息
• 当前行已经算过的左边信息

这就说明二维数组可以压成一维。

一维数组的含义

令 \( dp[j] \) 表示“当前处理到某一行时，该行第 \(j\) 列的最小路径和”。

那么更新时：

• 更新前的 dp[j] 表示上一行的值
• 更新后的 dp[j-1] 表示当前行左侧的值

于是 \( dp[j] = \min(dp[j],\ dp[j-1]) + a[i][j] \)

这正是滚动数组最值得体会的地方：同一个数组元素，在不同时间点含义不同。

int main() {
    vector<vector<int>> a = {
        {1, 3, 1},
        {1, 5, 1},
        {4, 2, 1}
    };

    int n = a.size(), m = a[0].size();
    vector<int> dp(m, 0);

    dp[0] = a[0][0];
    for (int j = 1; j < m; j++) dp[j] = dp[j - 1] + a[0][j];
    for (int i = 1; i < n; i++) {
        dp[0] += a[i][0];
        for (int j = 1; j < m; j++) {
            dp[j] = min(dp[j], dp[j - 1]) + a[i][j];
        }
    } cout << dp[m - 1] << "\n";
}

复杂度

空间复杂度已经降到 \( O(m) \)

很多动态规划问题，如果某些数据再也用不到了，都有可能有空间优化的可能。

第二题：加入障碍物或改变移动方式

有些格子是障碍，不能经过。其余格子有代价。仍然只能向右或向下，求从左上到右下的最小路径和。

如果 \((i,j)\) 是障碍，那么这个状态直接无效。可以把它看作正无穷。否则，若它不是障碍，才有正常转移：

和上一题相比，变化不大，但非常典型。它提醒我们：动态规划不是先背一个式子，而是先想“当前状态是否存在”，再想“它从哪里来”。

另一个经典升级方式，是不再只允许“右”和“下”两种动作。比如，允许向右下对角线行走。此时到达 \((i,j)\) 的最后一步可能来自三个位置：

• \((i-1,j)\)
• \((i,j-1)\)
• \((i-1,j-1)\)

所以 \( dp[i][j] = \min\{dp[i-1][j],\ dp[i][j-1],\ dp[i-1][j-1]\} + a[i][j] \)

当条件改变时，遇到新题时，一定要理清当前状态是什么？它能从哪些状态过来？

情况一下我们仍可应用滚动数组，而情况二下，除了“上方”和“左方”，还必须再额外保存“左上方”的旧值。最终仍只需要一维空间。

第三题：恰好经过 \(k\) 个特殊格子

现在我们还是要走格子，不过不是要最小化代价，而是要求出总方案数量。某些格子是“特殊格子”，要求从左上走到右下，路径上恰好经过 \(k\) 个特殊格子。这时如果你只记录当前坐标，就无法区分：

• 走到同一个位置，但已经经过了 1 个特殊格子
• 走到同一个位置，但已经经过了 3 个特殊格子

这两种情况显然不能混在一起。设 \( dp[i][j][t] \) 表示走到 \((i,j)\) 时，恰好经过了 \(t\) 个特殊格子的方案数。

设 \(special(i,j)\) 表示当前格子是否特殊，取值为 \(0\) 或 \(1\)。那么从上方或左方转移过来时，特殊格子的数量要跟着变化：\( dp[i][j][t] = dp[i-1][j][t-special(i,j)] + dp[i][j-1][t-special(i,j)] \)

当然，这个式子只在下标合法时成立。为了简化边界判断，有不合法下标的项就直接取 0.

int main() {
    int n = 3, m = 3, K = 2;
    vector<vector<int>> sp = {
        {0, 1, 0},
        {1, 0, 1},
        {0, 0, 1}
    };

    vector<vector<vector<long long>>> dp(
        n, vector<vector<long long>>(m, vector<long long>(K + 1, 0))
    );

    if (sp[0][0] <= K) dp[0][0][sp[0][0]] = 1;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (i == 0 && j == 0) continue;

            int add = sp[i][j];
            for (int t = add; t <= K; t++) {
                if (i > 0) dp[i][j][t] += dp[i - 1][j][t - add];
                if (j > 0) dp[i][j][t] += dp[i][j - 1][t - add];
            }
        }
    } cout << dp[n - 1][m - 1][K] << "\n";
}

第四题：双人走格子

两个人同时从左上角走到右下角，每次都只能向右或向下。每个格子有收益，但如果两个人经过同一个格子，这个格子的收益只能算一次，问总收益最大是多少。

这个模型也可以理解成：一个人从起点走到终点，再从终点走回来，经过的格子不能重复计分。

最直接的想法是：\( dp[x_1][y_1][x_2][y_2] \) 表示两个人分别走到 \((x_1,y_1)\) 和 \((x_2,y_2)\) 的最优收益。这样的维度太高了，既难写，也不优雅。

压缩空间

如果两个人都从起点出发，每次都只走一步，那么当他们“同时”走到某个阶段时，步数一定相同。

设当前总步数为 \(k\)，那么：

• 第一个人在 \((i_1,\ k-i_1)\)
• 第二个人在 \((i_2,\ k-i_2)\)

于是四维状态就可以压成三维：

表示两个人都走了 \(k\) 步时，分别位于上述两个位置时的最大收益。

转移

因为每个人每一步只有“向下”或“向右”两种选择，所以两个人合起来一共有四种转移来源：

• 两人都从上面来
• 第一个从上面来，第二个从左边来
• 第一个从左边来，第二个从上面来
• 两人都从左边来

所以当前状态的来源是四个候选状态中的最大值，再加上当前位置的收益。设两人当前位置分别是 \((x_1,y_1)\) 和 \((x_2,y_2)\)，则本轮新增收益为：

int main() {
    int n = 3;
    vector<vector<int>> a = {
        {1, 2, 3},
        {0, 4, 5},
        {2, 1, 6}
    };

    const int NEG = -1e9;
    vector<vector<vector<int>>> dp(
        2 * n - 1, vector<vector<int>>(n, vector<int>(n, NEG))
    );

    dp[0][0][0] = a[0][0];

    for (int k = 1; k <= 2 * n - 2; k++) {
        for (int i1 = 0; i1 < n; i1++) {
            for (int i2 = 0; i2 < n; i2++) {
                int j1 = k - i1;
                int j2 = k - i2;
                if (j1 < 0 || j1 >= n || j2 < 0 || j2 >= n) continue;

                int best = NEG;

                for (int di1 = 0; di1 <= 1; di1++) {
                    for (int di2 = 0; di2 <= 1; di2++) {
                        int pi1 = i1 - di1;
                        int pi2 = i2 - di2;
                        int pj1 = (k - 1) - pi1;
                        int pj2 = (k - 1) - pi2;
                        if (pi1 < 0 || pi2 < 0 || pj1 < 0 || pj2 < 0) continue;
                        best = max(best, dp[k - 1][pi1][pi2]);
                    }
                }

                if (best == NEG) continue;

                int gain = a[i1][j1];
                if (i1 != i2 || j1 != j2) gain += a[i2][j2];
                dp[k][i1][i2] = best + gain;
            }
        }
    } cout << dp[2 * n - 2][n - 1][n - 1] << "\n";
}

总结

“走格子”看起来像一类很小的题型，但它其实浓缩了动态规划里最核心的东西：

• 状态设计
• 前驱分析
• 边界初始化
• 遍历顺序
• 空间优化
• 维度扩展

我们需要设计：状态是什么？需要几个维度来表示？当前状态从哪里来？边界和初始条件从哪里来？遍历的顺序是什么？

文章来源:https://www.cnblogs.com/ofnoname/p/19800499
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！