【动态规划 / 总结必看】从一道入门题与你分享关于 DP 的分析技巧 ...

前言

今天，我们开启动态规划的第一个系列：不同路径问题。

由于 DP 是一个很大的话题，对应的模型也很多，所以不好说这个动态规划系列会持续多久。

我也会根据你们的反馈来决定要不要继续讲解某个 DP 模型的题目，还是说跳到下一个 DP 模型。

举个🌰，假如你们觉得线性 DP 可以了，那我们就进入区间 DP，一层层的到达树形 DP、插头 DP、斜率 DP ...

如果觉得昏头了，那我们就停下来讲点别的类型的题目。有时候停下来沉淀一下也很不错 ~

今天也是 3.8 女神节，给各位 女神 节日快乐 ~

题目描述

这是 LeetCode 上的 62. 不同路径，难度为 Medium。

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

输入：m = 3, n = 7输出：28

示例 2：

输入：m = 3, n = 2输出：3解释：从左上角开始，总共有 3 条路径可以到达右下角。1. 向右 -> 向下 -> 向下2. 向下 -> 向下 -> 向右3. 向下 -> 向右 -> 向下

示例 3：

输入：m = 7, n = 3输出：28

示例 4：

输入：m = 3, n = 3输出：6

提示：

• 1 <= m, n <= 100

• 题目数据保证答案小于等于 2 * $10^9$

动态规划解法

定义 f[i][j] 为到达位置 (i,j) 的不同路径数量。

那么 f[n-1][m-1] 就是我们最终的答案，而 f[0][0] = 1 是一个显而易见的起始条件。

由于题目限定了我们只能 往下 或者 *往右* 移动，因此我们按照当前可选方向进行分析：

1. 当前位置只能 往下 移动，即有 f[i][j] = f[i-1][j]
   

1. 当前位置只能 往右 移动，即有 f[i][j] = f[i][j-1]
   

1. 当前位置即能 往下 也能 往右 移动，即有 f[i][j] = f[i][j-1] + f[i-1][j]
   

代码：

class Solution {    public int uniquePaths(int m, int n) {        int[][] f = new int[m][n];        f[0][0] = 1;        for (int i = 0; i < m; i++) {            for (int j = 0; j < n; j++) {                if (i > 0 && j > 0) {                    f[i][j] = f[i - 1][j] + f[i][j - 1];                } else if (i > 0) {                    f[i][j] = f[i - 1][j];                } else if (j > 0) {                    f[i][j] = f[i][j - 1];                }            }        }        return f[m - 1][n - 1];    }}

• 时间复杂度：$O(n*m)$

• 空间复杂度：$O(n*m)$

总结

这是一道很简单的动态规划入门题目，相信很多同学都做过。

如果我们真正静下来思考这道题的话，会发现还是有很多有价值的东西可以挖掘的。

1. 我们是如何确定本题可以使用动态规划来解决的？

通常我们要从有无后效性进行入手分析。

如果对于某个状态，我们可以只关注状态的值，而不需要关注状态是如何转移过来的话，那么这就是一个无后效性的问题，可以考虑使用 DP 解决。

另外一个更加实在的技巧，我们还可以通过 数据范围 来猜测是不是可以用 DP 来做。

因为 DP 是一个递推的过程，因此如果数据范围是 $10^5$~$10^6$ 的话，可以考虑是不是可以使用一维 DP 来解决；如果数据范围是 $10^2$~$10^3$ 的话，可以考虑是不是可以使用二维 DP 来做 ...

2. 我们是如何确定本题的状态定义的？

说实话，DP 的状态定义很大程度是靠经验去猜的。

虽然大多数情况都是猜的，但也不是毫无规律，相当一部分题目的状态定义是与结尾和*答案*有所关联的。

3. 我们是如何确定状态转移方程的？

通常来说，如果我们的状态定义猜对了，状态转移方程就是对最后一步的分情况讨论。

如果我们有一个对的状态定义的话，基本上状态转移方程就是呼之欲出。

因此一定程度上，状态转移方程可以反过来验证我们状态定义猜得是否正确：

如果猜了一个状态定义，然后发现无法列出涵盖所有情况（不漏）的状态转移方程，多半就是状态定义猜错了，赶紧换个思路，而不是去死磕状态转移方程。

4. 对状态转移的要求是什么？

我们的状态转移是要做到不漏还是*不重不漏*取决于问题本身：

• 如果是求最值的话，我们只需要确保不漏即可，因为重复不影响结果。

• 如果是求方案数的话，我们需要确保不重不漏。

5. 我们是如何分析动态规划的时间复杂度的？

对于动态规划的复杂度/计算量分析，有多少个状态，复杂度/计算量就是多少。

因此一维 DP 的复杂度通常是线性的 $O(n)$，而二维 DP 的复杂度通常是平方的 $O(n^2)$。

建议

这些关于动态规划的小技巧，我希望你在动态规划专题的第一课就学到。

同时，我十分建议刚读完总结的你再回头看一遍题解，看看我们这些分析技巧是否都能套入分析思路。

带着这个感觉，随着我们动态规划专题的进行而不断强化，相信你会在动态规划这个知识点上突飞猛进。

思考

如果我们不限制只能往右和*往下*移动的话，还能使用 DP 来做吗？

最后

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

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

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

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