【动态规划/路径问题】强化忽略「状态定义」&「转移方程」来求解 DP 的「技巧解法

前言

今天是我们讲解「动态规划专题」中的 路径问题 的第九天。

我在文章结尾处列举了我所整理的关于「路径问题」的相关题目。

「路径问题」我会按照编排好的顺序进行讲解（一天一道）。

你也先可以尝试做做，也欢迎你向我留言补充，你觉得与路径相关的 DP 类型题目 ~

题目描述

这是 LeetCode 上的「576. 出界的路径数」，难度为 Medium。

给定一个 的网格和一个球。

球的起始坐标为 ，你可以将球移到相邻的单元格内，或者往上、下、左、右四个方向上移动使球穿过网格边界。

但是，你最多可以移动 次。

找出可以将球移出边界的路径数量。答案可能非常大，返回结果 mod + 7 的值。

示例 1：

输入: m = 2, n = 2, N = 2, i = 0, j = 0
输出: 6

解释:

示例 2：

输入: m = 1, n = 3, N = 3, i = 0, j = 1
输出: 12

解释:

说明:

• 球一旦出界，就不能再被移动回网格内。
• 网格的长度和高度在 的范围内。
• 在 的范围内。

回顾

还记得我在 上一节 和你说的两种「动态规划」求解方法吗？

我们来回顾一下：

1. 根据经验猜一个「状态定义」，然后根据「状态定义」去推导一个「状态转移方程」。

2. 先写一个「记忆化搜索」解法，再将「记忆化搜索」改写成「动态规划」。

为了方便区分这两种方法，我们称第一种解法为「经验解法」，第二种为「技巧解法」吧。

其中「技巧解法」是我上一节教你的，今天我们也将使用这种解法解决本题。

来强化我们对「技巧解法」的熟练度。

动态规划

由于我们的「技巧解法」是将「记忆化搜索」翻译成「动态规划」。

因此我们需要先有一个「记忆化搜索」解法。

但我在 上一节 的「总结」部分也跟你强调过，所谓的有一个「记忆化搜索」，我们只需要考虑 DFS 函数会如何设计即可，而不需要真正去实现一个「记忆化搜索」。

那么如果是让你设计一个 DFS 函数来解决本题，你会如何设计？

如果是我的话，我大概会这样设计：

int dfs(int m, int n, int x, int y, int k) {}

其中 和 是对应了题目的源输入，用来表示矩形是几行几列的，整个 DFS 过程都不会发生变化，因此我们无须理会。

代表当前所在的位置， 代表最多的移动次数，返回值代表路径数量。

重点放在 DFS 函数签名中的「可变参数」与「返回值」。这和我们【动态规划】中的「状态定义」强关联。

同时为了方便，我们可以将 根据以下规则映射为一个独立的编号 ：

index = x * n + y;
(x, y) = (index / n, index % n);

根据我们的「技巧解法」，我们可以设计一个二维数组 作为我们的 dp 数组：

• 第一维代表 DFS 可变参数中的 所对应 。取值范围为
• 第二维代表 DFS 可变参数中的 。取值范围为

dp 数组中存储的就是我们 DFS 的返回值：路径数量。

根据 dp 数组中的维度设计和存储目标值，我们可以得知「状态定义」为：

代表从位置 出发，可用步数不超过 时的路径数量。

至此，我们没有实现「记忆化搜索」，只是设计了 DFS 函数的签名，就已经得出我们的「状态定义」了，接下来需要考虑「转移方程」。

当有了「状态定义」之后，我们需要从「最后一步」来推导出「转移方程」：

由于题目允许往四个方向进行移动。

因此我们的最后一步也要统计四个相邻的方向。

举个?，假设我们当前位置为，而 四个方向的相邻格子均不超出矩形。即有：

出发的路径数量 = 上方 的路径数量 + 下方 的路径数量 + 左方 的路径数量 + 右方 (x,y+1)$ 的路径数量

由此可得我们的状态转移方程：

PS. 转移方程中 dp 数组的第一维存储的是 对应的 。

从转移方程中我们发现，更新 依赖于 ，因此我们转移过程中需要将最大移动步数进行从小到大枚举。

至此，我们已经完成求解「路径规划」问题的两大步骤：「状态定义」&「转移方程」。

但这还不是所有，我们还需要一些「有效值」来滚动下去。

其实就是需要一些「有效值」作为初始化状态。

观察我们的「转移方程」可以发现，整个转移过程是一个累加过程，如果没有一些有效的状态（非零值）进行初始化的话，整个递推过程并没有意义。

那么哪些值可以作为成为初始化状态呢？

显然，当我们已经位于矩阵边缘的时候，我们可以一步跨出矩阵，这算作一条路径。

同时，由于我们能够往四个方向进行移动，因此不同的边缘格子会有不同数量的路径。

换句话说，我们需要先对边缘格子进行初始化操作，预处理每个边缘格子直接走出矩阵的路径数量。

目的是为了我们整个 DP 过程可以有效的递推下去。

代码：

class Solution {
    int mod = (int)1e9+7;
    int m, n, N;
    public int findPaths(int _m, int _n, int _N, int _i, int _j) {
        m = _m; n = _n; N = _N;
        
        // f[i][j] 代表从 idx 为 i 的位置出发，移动步数不超过 j 的路径数量
        int[][] f = new int[m * n][N + 1];
        
        // 初始化边缘格子的路径数量
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0) add(i, j, f);
                if (i == m - 1) add(i, j, f);
                if (j == 0) add(i, j, f);
                if (j == n - 1) add(i, j, f);
            }
        }
        
        // 定义可移动的四个方向
        int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
        
        // 从小到大枚举「可移动步数」
        for (int step = 1; step <= N; step++) {
            // 枚举所有的「位置」
            for (int k = 0; k < m * n; k++) {
                int x = parseIdx(k)[0], y = parseIdx(k)[1];
                for (int[] d : dirs) {
                    int nx = x + d[0], ny = y + d[1];
                    // 如果位置有「相邻格子」，则「相邻格子」参与状态转移
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                        f[k][step] += f[getIndex(nx, ny)][step - 1];
                        f[k][step] %= mod;
                    }
                }
            }
        }
        
        // 最终结果为从起始点触发，最大移动步数不超 N 的路径数量
        return f[getIndex(_i, _j)][N];
    }
    
    // 为每个「边缘」格子，添加一条路径
    void add(int x, int y, int[][] f) {
        int idx = getIndex(x, y);
        for (int step = 1; step <= N; step++) {
            f[idx][step]++;
        }
    }
    
    // 将 (x, y) 转换为 index
    int getIndex(int x, int y) {
        return x * n + y;
    }
    
    // 将 index 解析回 (x, y)
    int[] parseIdx(int idx) {
        return new int[]{idx / n, idx % n};
    }
} 

• 时间复杂度：共有 个状态需要转移，复杂度为
• 空间复杂度：

总结

如果你有理解透彻 路径问题第八讲 中的内容的话，今天这道题应该是一道练习题。

帮助你加强对【动态规划】中的「技巧解法」的掌握。

如果你已经认真学过 路径问题第八讲，但是还是觉得本题难以入手，也没有关系。

我教给你都是【动态规划】中的通解，真正理解掌握往往需要多重复。

重复不仅仅是指你要多刷题，而是要始终带着我与你分享的「分析思路」去解决动态规划问题。

最后，我十分建议你将 路径问题 系列的每一讲多看几遍，这些内容不仅仅是「路径问题」相关题解，更是【动态规划】问题的通用解决方案。

这些都是三叶多年 OI 经历所总结的精华，希望你会认真的看哦 ~

路径问题（目录）

62.不同路径（中等）：路径问题第一讲

63.不同路径 II（中等）：路径问题第二讲

64.最小路径和（中等）：路径问题第三讲

120.三角形最小路径和（中等）：路径问题第四讲

931.下降路径最小和（中等）：路径问题第五讲

1289.下降路径最小和 II（困难）：路径问题第六讲

1575.统计所有可行路径（困难）：路径问题第七讲（记忆化搜索）

1575.统计所有可行路径（困难）：路径问题第八讲（动态规划）

576.出界的路径数（中等）：本篇

1301.最大得分的路径数目（困难）

欢迎补充 ~

最后

这是我们「刷穿 LeetCode」系列文章的第 No.576 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。