前言
今天,我们开启动态规划的第一个系列:不同路径问题。
由于 DP 是一个很大的话题,对应的模型也很多,所以不好说这个动态规划系列会持续多久。
我也会根据你们的反馈来决定要不要继续讲解某个 DP 模型的题目,还是说跳到下一个 DP 模型。
举个🌰,假如你们觉得线性 DP 可以了,那我们就进入区间 DP,一层层的到达树形 DP、插头 DP、斜率 DP ...
如果觉得昏头了,那我们就停下来讲点别的类型的题目。有时候停下来沉淀一下也很不错 ~
题目描述
这是 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 * 10910^9109
动态规划解法
定义 f[i][j]
为到达位置 (i,j)
的不同路径数量。
那么 f[n-1][m-1]
就是我们最终的答案,而 f[0][0] = 1
是一个显而易见的起始条件。2
由于题目限定了我们只能 往下 或者 往右 移动,因此我们按照当前可选方向进行分析:
- 当前位置只能 往下 移动,即有
f[i][j] = f[i-1][j]
- 当前位置只能 往右 移动,即有
f[i][j] = f[i][j-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)O(n∗m)
- 空间复杂度:O(n∗m)O(n*m)O(n∗m)
总结
这是一道很简单的动态规划入门题目,相信很多同学都做过。
如果我们真正静下来思考这道题的话,会发现还是有很多有价值的东西可以挖掘的。
1. 我们是如何确定本题可以使用动态规划来解决的?
通常我们要从有无后效性进行入手分析。
如果对于某个状态,我们可以只关注状态的值,而不需要关注状态是如何转移过来的话,那么这就是一个无后效性的问题,可以考虑使用 DP 解决。
另外一个更加实在的技巧,我们还可以通过 数据范围 来猜测是不是可以用 DP 来做。
因为 DP 是一个递推的过程,因此如果数据范围是 10510^510510610^6106 的话,可以考虑是不是可以使用一维 DP 来解决;如果数据范围是 10210^210210310^3103 的话,可以考虑是不是可以使用二维 DP 来做 ...
2. 我们是如何确定本题的状态定义的?
说实话,DP 的状态定义很大程度是靠经验去猜的。
虽然大多数情况都是猜的,但也不是毫无规律,相当一部分题目的状态定义是与结尾和答案有所关联的。
3. 我们是如何确定状态转移方程的?
通常来说,如果我们的状态定义猜对了,状态转移方程就是对最后一步的分情况讨论。
如果我们有一个对的状态定义的话,基本上状态转移方程就是呼之欲出。
因此一定程度上,状态转移方程可以反过来验证我们状态定义猜得是否正确:
如果猜了一个状态定义,然后发现无法列出涵盖所有情况(不漏)的状态转移方程,多半就是状态定义猜错了,赶紧换个思路,而不是去死磕状态转移方程。
4. 对状态转移的要求是什么?
我们的状态转移是要做到不漏还是不重不漏取决于问题本身:
- 如果是求最值的话,我们只需要确保不漏即可,因为重复不影响结果。
- 如果是求方案数的话,我们需要确保不重不漏。
5. 我们是如何分析动态规划的时间复杂度的?
对于动态规划的复杂度/计算量分析,有多少个状态,复杂度/计算量就是多少。
因此一维 DP 的复杂度通常是线性的 O(n)O(n)O(n),而二维 DP 的复杂度通常是平方的 O(n2)O(n^2)O(n2)。
建议
这些关于动态规划的小技巧,我希望你在动态规划专题的第一课就学到。
同时,我十分建议刚读完总结的你再回头看一遍题解,看看我们这些分析技巧是否都能套入分析思路。
带着这个感觉,随着我们动态规划专题的进行而不断强化,相信你会在动态规划这个知识点上突飞猛进。
思考
如果我们不限制只能往右和往下移动的话,还能使用 DP 来做吗?
最后
这是我们「刷穿 LeetCode」系列文章的第 No.62
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。