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

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

前言



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


由于 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


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


  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];
    }
}
复制代码


  • 时间复杂度:O(n∗m)O(n*m)O(nm)
  • 空间复杂度:O(n∗m)O(n*m)O(nm)


总结



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


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


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 原题链接和其他优选题解。

相关文章
|
存储 数据采集 人工智能
如何设计一个监控平台(上篇)
在大型分布式微服务场景下,各个服务版本快速迭代,各类业务规模不断膨胀,同时监控的场景也在不断的发生变化,线上故障随时可能发生,各个平台错综复杂,如何保证线上服务稳定运行,同时提升运维效率,降低运维成本成了监控平台的挑战。
如何设计一个监控平台(上篇)
|
开发框架 Java 数据库
java----包的命名规范
对包的解释与命名规则
10381 0
java----包的命名规范
|
存储 弹性计算 网络安全
|
8月前
|
存储 缓存 自然语言处理
浏览量超 10w 的热图,描述 RAG 的主流架构
大模型性能的持续提升,进一步挖掘了 RAG 的潜力,RAG 将检索系统与生成模型相结合,带来诸多优势,如实时更新知识、降低成本等。点击本文,为您梳理 RAG 的基本信息,并介绍提升大模型生成结果的方法,快一起看看吧~
721 115
|
11月前
|
机器学习/深度学习 人工智能 TensorFlow
人工智能浪潮下的自我修养:从Python编程入门到深度学习实践
【10月更文挑战第39天】本文旨在为初学者提供一条清晰的道路,从Python基础语法的掌握到深度学习领域的探索。我们将通过简明扼要的语言和实际代码示例,引导读者逐步构建起对人工智能技术的理解和应用能力。文章不仅涵盖Python编程的基础,还将深入探讨深度学习的核心概念、工具和实战技巧,帮助读者在AI的浪潮中找到自己的位置。
|
10月前
|
存储 设计模式 算法
命令模式(Command Pattern)
命令模式是一种行为型设计模式,将请求封装为对象,实现参数化请求、支持撤销操作和记录日志。适用于需要解耦发送者和接收者的场景,如智能家居系统中的遥控器控制电灯开关并支持撤销功能。优点包括解耦、支持撤销与恢复操作,但过度使用会增加系统复杂度。
163 7
|
12月前
|
设计模式 网络协议 Java
04.原型模式设计思想
本文详细介绍了原型模式的设计思想,包括其定义、应用场景、实现原理及优缺点。通过邮件复制的例子,阐述了原型模式如何通过克隆现有对象来创建新对象,从而提高性能和减少代码复杂度。文章还对比了原型模式与工厂模式的区别,并讨论了深克隆和浅克隆的实现方式。最后,总结了原型模式在特定场景下的应用价值和局限性。
113 1
|
存储 缓存 Linux
内存学习(四):内存映射1
内存学习(四):内存映射1
448 0
|
关系型数据库 MySQL 数据库
【已解决】ERROR 1045 - Access denied for user ‘root‘@‘localhost‘ (using password: YES)
【已解决】ERROR 1045 - Access denied for user ‘root‘@‘localhost‘ (using password: YES)
|
关系型数据库 MySQL 数据库
连接mysql报Access denied for user 'root'@'localhost'错误的解决办法
连接mysql报Access denied for user 'root'@'localhost'错误的解决办法
1322 0