【动态规划/总结必看】从一道入门题与你分享关于 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 *

动态规划解法

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

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

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

1. 当前位置只能 「往下」 移动，即有 f[i][j] = f[i-1][j]
2. 当前位置只能 「往右」 移动，即有 f[i][j] = f[i][j-1]
3. 当前位置即能 「往下」 也能 「往右」 移动，即有 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];
    }
}

• 时间复杂度：

• 空间复杂度：

总结

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

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

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

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

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

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

因为 DP 是一个递推的过程，因此如果数据范围是

~

的话，可以考虑是不是可以使用一维 DP 来解决；如果数据范围是

~

的话，可以考虑是不是可以使用二维 DP 来做 ...

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

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

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

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

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

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

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

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

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

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

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

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

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

因此一维 DP 的复杂度通常是线性的

，而二维 DP 的复杂度通常是平方的

。

建议

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

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

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

思考

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

最后

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

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

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

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