【动态规划/路径问题】如何忽略「状态定义」&「转移方程」来实现动态规划 ...

前言

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

昨天我向你讲解了 1575. 统计所有可行路径 的「记忆化搜索」解法。

今天我们将讲解「1575. 统计所有可行路径」中的「动态规划」解法。

另外，我想强调对于任何算法题，无论难度 tag 是什么。在没见过同类题时，是很难想到怎么做的。因此做不出十分正常，大家千万不要因此失去信心。

做算法是一个增加自信的过程，而不是失去信心的过程。

一道题原本完全没有思路，看了题解之后理解了。

下次遇到能做出来，或者不至于毫无思路。这本身就已经是一种进步了 ~

所以大家加油呀? ~

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

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

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

题目描述

这是 LeetCode 上的「1575. 统计所有可行路径」，难度为 Hard。

给你一个 互不相同 的整数数组，其中 表示第 个城市的位置。

同时给你 ， 和 分别表示出发城市、目的地城市 和 你初始拥有的汽油总量。

每一步中，如果你在城市 ，你可以选择任意一个城市 ，满足 且 ，并移动到城市 。

从城市 移动到 消耗的汽油量为 ， 表示 的绝对值。

请注意， 任何时刻都不能为负，且你可以经过任意城市超过一次（包括 和 ）。

请你返回从 到 所有可能路径的数目。

由于答案可能很大，请将它对 + 7 取余后返回。

示例 1：

输入：
locations = [2,3,6,8,4], 
start = 1, 
finish = 3, 
fuel = 5

输出：4

解释：以下为所有可能路径，每一条都用了 5 单位的汽油：
1 -> 3
1 -> 2 -> 3
1 -> 4 -> 3
1 -> 4 -> 2 -> 3

示例 2：

输入：
locations = [4,3,1], 
start = 1, 
finish = 0, 
fuel = 6

输出：5

解释：以下为所有可能的路径：
1 -> 0，使用汽油量为 fuel = 1
1 -> 2 -> 0，使用汽油量为 fuel = 5
1 -> 2 -> 1 -> 0，使用汽油量为 fuel = 5
1 -> 0 -> 1 -> 0，使用汽油量为 fuel = 3
1 -> 0 -> 1 -> 0 -> 1 -> 0，使用汽油量为 fuel = 5

示例 3：

输入：
locations = [5,2,1], 
start = 0, 
finish = 2, 
fuel = 3

输出：0

解释：没有办法只用 3 单位的汽油从 0 到达 2 。
因为最短路径需要 4 单位的汽油。

示例 4 ：

输入：
locations = [2,1,5], 
start = 0, 
finish = 0, 
fuel = 3

输出：2

解释：总共有两条可行路径，0 和 0 -> 1 -> 0 。

示例 5：

输入：
locations = [1,2,3], 
start = 0, 
finish = 2, 
fuel = 40

输出：615088286

解释：路径总数为 2615088300 。
将结果对 10^9 + 7 取余，得到 615088286 。

提示：

• 2 <= locations.length <= 100
• 1 <= locations[i] <=
• 所有 locations 中的整数 互不相同
• 0 <= start, finish < locations.length
• 1 <= fuel <= 200

回顾

本题的「记忆化搜索」部分在这里：1575. 统计所有可行路径【上集】

昨天，我跟你提到过了今天的内容：

1. 如何将「记忆化搜索」改成「动态规划」。
2. 如果 的数据范围从 改为 ，如何求解。

我们今天先来讲解第 1 点，第 2 点会放到一个单独的【番外篇】。

目的是为了控制每篇文章字数在 4k 以内，不至于一下子灌输太多内容。

动态规划

我先看下上一节「记忆化搜索」中的代码。

可以着重留意 DFS 部分的代码：

class Solution {
    int mod = 1000000007;
    int[][] cache;
    public int countRoutes(int[] ls, int start, int end, int fuel) {
        int n = ls.length;
        cache = new int[n][fuel + 1];
        for (int i = 0; i < n; i++) {
            Arrays.fill(cache[i], -1);
        }
        return dfs(ls, start, end, fuel);
    }
    
    /**
     * 计算「路径数量」
     * @param ls 入参 locations
     * @param u 当前所在位置（ls 的下标）
     * @param end 目标哦位置（ls 的下标）
     * @param fuel 剩余油量
     * @return 在位置 u 出发，油量为 fuel 的前提下，到达 end 的「路径数量」
     */
    int dfs(int[] ls, int u, int end, int fuel) {
        if (cache[u][fuel] != -1) {
            return cache[u][fuel];
        }
        
        int need = Math.abs(ls[u] - ls[end]);
        if (need > fuel) {
            cache[u][fuel] = 0;
            return 0;
        }
        
        int n = ls.length;
        int sum = u == end ? 1 : 0;
        for (int i = 0; i < n; i++) {
            if (i != u) {
                need = Math.abs(ls[i] - ls[u]);
                if (fuel >= need) {
                    sum += dfs(ls, i, end, fuel - need);
                    sum %= mod;
                }
            }
        }
        cache[u][fuel] = sum;
        return sum;
    }
}

接下来，我将会教你如何直接将「记忆化搜索」改成「动态规划」。

使用这种技巧，你将不需要去猜「状态定义」和根据「状态定义」推导「状态转移方程」。

我们重点关注下我们的 DFS 方法签名设计：

int dfs(int[] ls, int u, int end, int fuel) {}

其中， 参数和 参数分别代表源输入的 和 ，在整个 DFS 过程都不会变化，属于不变参数。

而 参数和 参数则是代表了 DFS 过程中的当前位置和当前油量，属于变化参数。

因此我们可以定一个 二维数组，来分别表示两个可变参数。

第一维代表当前位置（对应 数组的下标），第二维代表当前剩余油量。

二维数组中存储的就是我们的 DFS 方法的返回值（路径数量）。

同时结合题意，不难得知维度的取值范围：

• 第一维的取值范围为
• 第二维的取值范围为

做完这一步的”翻译“工作，我们就得到了「动态规划」的「状态定义」了。

代表从位置 出发，当前剩余油量为 的前提下，到达目的地的路径数量。

不知道你是否发现，这个「状态定义」和我们「记忆化搜索」中的缓存器的定义是一致的。

接下来我们要从 DFS 中”翻译“出「状态转移方程」。

所谓的「状态转移方程」其实就是指如何从一个状态转移到另外一个状态。

而我们的 DFS 主逻辑就是完成这个转移的。

DFS 中的主逻辑很简单：枚举所有的位置，看从当前位置 出发，可以到达的位置有哪些。

于是我们很容易就可以得出状态转移方程：

代表计算位置 油量 的状态时枚举的「下一位置」， 代表从 到达 需要的油量。

从状态转移方程可以发现，在计算 的时候依赖于 。

其中 和 并无严格的大小关系，而 和 具有严格的大小关系（）。

因此我们需要先从小到大枚举油量这一维。

代码：

class Solution {
    int mod = 1000000007;
    public int countRoutes(int[] ls, int start, int end, int fuel) {
        int n = ls.length;

        // f[i][j] 代表从位置 i 出发，当前油量为 j 时，到达目的地的路径数
        int[][] f = new int[n][fuel + 1];
        
        // 对于本身位置就在目的地的状态，路径数为 1
        for (int i = 0; i <= fuel; i++) f[end][i] = 1;

        // 从状态转移方程可以发现 f[i][fuel]=f[i][fuel]+f[k][fuel-need]
        // 在计算 f[i][fuel] 的时候依赖于 f[k][fuel-need]
        // 其中 i 和 k 并无严格的大小关系
        // 而 fuel 和 fuel-need 具有严格大小关系：fuel >= fuel-need
        // 因此需要先从小到大枚举油量
        for (int cur = 0; cur <= fuel; cur++) {
            for (int i = 0; i < n; i++) {
                for (int k = 0; k < n; k++) {
                    if (i != k) {
                        int need = Math.abs(ls[i] - ls[k]);
                        if (cur >= need) {
                            f[i][cur] += f[k][cur-need];
                            f[i][cur] %= mod;
                        }
                    }
                }
            }
        }
        return f[start][fuel];
    }
}

• 时间复杂度：最坏情况下共有 个状态需要计算（填满整个 数组）。每计算一个状态需要遍历一次 数组，复杂度为 。整体复杂度为
• 空间复杂度：

至此，我们只利用 DFS 的方法签名与主逻辑，就写出了「动态规划」解法。

我再帮你来总结一下这个过程：

1. 从 DFS 方法签名出发。分析哪些入参是可变的，将其作为 DP 数组的维度；将返回值作为 DP 数组的存储值。

2. 从 DFS 的主逻辑可以抽象中单个状态的计算方法。

其中第一点对应了「动态规划」的「状态定义」，第二点对应了「动态规划」的「状态方程转移」。

我希望你借此好好体会一下「记忆化搜索」与「动态规划」的联系。

总结

今天，我与你分享了如何直接将「记忆化搜索」改成「动态规划」，而无需关心具体的「状态定义」和「状态转移方程」。

到目前为止，我们已经掌握了两种求解「动态规划」问题的方法：

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

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

其中第一种是我们前几节（1 ~ 6）用到的方法，而第二种是我本节给你介绍的方法。

能够去猜「状态定义」或者使用「记忆化搜索」求解，都有一个大前提：问题本身具有无效性。

由于「动态规划」的状态定义猜测，是一门很讲求经验的技能。

因此对于那些你接触过的模型，我建议你使用第一种方式；

如果遇到一道你从来没接触过的题目时，我建议你先想想「记忆化搜索」该如何实现，然后反推出「动态规划」。

这里说的想想「记忆化搜索」该如何实现，不需要真正动手实现一个「记忆化搜索」解法，而只需要想清楚，如果使用「记忆化搜索」的话，我的 DFS 函数签名如何设计即可。

当搞清楚「记忆化搜索」的函数签名设计之后，「状态定义」部分基本就已经出来了，之后的「状态转移方程」就还是一样的分析方法。

当然，如果你觉得「记忆化搜索」更好实现的话，大可直接使用「记忆化搜索」求解，不一定需要将其转化为「动态规划」。

因为由「记忆化搜索」直接转过来的「动态规划」，两者复杂度是一样的。而且通常「记忆化搜索」的实现难度通常要低很多。

路径问题（目录）

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

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

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

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

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

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

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

1575.统计所有可行路径（困难）：本篇（动态规划）

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

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

欢迎补充 ~

思考&进阶

复杂度的算法只能支撑我们解决 的数据，如果数据范围出到 呢？

接下来我们该考虑如何优化 DP。

还是和以前一样，要想知道如何优化，先要剖析现有算法做了些什么工作：

1. 转移 个状态
2. 每次状态需要枚举 个点

通常需要转移的状态数量是无法减少的（空间复杂度会相对难优化），因此我们很难从第 1 点进行入手。

那么我们该如何优化第 2 点呢？

如果你学有余力，我建议你可以将其作为一个思考题。

如果你觉得今天内容已经够多了，也没有关系。

好好理解今天的内容就已经足够了，要知道我们今天的解法就是一道 Hard 题的标准解法。

这个优化手段涉及到「拆分集合等效转换」概念，超出了本系列课程的难度，我将作为「番外篇」进行介绍。

最后

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

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

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

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