今天,我们开启「动态规划」的第一个系列:「不同路径」问题。
由于 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
提示:
定义 f[i][j]
为到达位置 (i,j)
的不同路径数量。
那么 f[n-1][m-1]
就是我们最终的答案,而 f[0][0] = 1
是一个显而易见的起始条件。
由于题目限定了我们只能 往下 或者 往右 移动,因此我们按照「当前可选方向」进行分析:
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];
}
}
这是一道很简单的动态规划入门题目,相信很多同学都做过。
如果我们真正静下来思考这道题的话,会发现还是有很多有价值的东西可以挖掘的。
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 原题链接和其他优选题解。