没有合适的资源?快使用搜索试试~ 我知道了~
首页《代码随想录》动态规划深度解析PDF
《代码随想录》动态规划深度解析PDF
需积分: 0 2 下载量 29 浏览量
更新于2024-06-25
收藏 8.74MB PDF 举报
"《动态规划专题精讲(v2.0).pdf》是由程序员Carl编写的,聚焦于动态规划这一重要算法领域的深入解析。该PDF文档包含了8万字的详细内容,50多张分析图表,以及50篇精心挑选的文章,总计200页。文档覆盖了40多道LeetCode上的经典动态规划题目,旨在帮助读者掌握这一复杂而关键的算法概念。" 在动态规划方面,此PDF的特点在于其严谨和系统性的讲解方式。与网络上稀少且难以理解的动态规划资料相比,《动态规划专题精讲》通过50篇精品文章深入浅出地剖析了这一主题。作者Carl指出,动态规划的难点不仅在于理解和应用,更在于如何清晰地传授给他人。常见的算法书籍如《剑指Offer》对此的讲解较为简略,而《算法4》和《算法导论》则分别未涉及或难度过高。 为了克服这些困难,Carl倾注大量精力,构建了一套完整的动态规划方法论,确保每个问题都能被彻底解析。虽然主要使用C++进行代码演示,但该PDF的核心思想和算法逻辑同样适用于其他编程语言,如Java、Python、Go和JavaScript。 此外,Carl还创建了名为"代码随想录"的在线刷题网站www.programmercarl.com,提供多种语言版本的支持,以便读者能够实践和巩固所学。同时,这个项目也在GitHub上开源,网址为https://github,鼓励社区参与和交流。 通过学习《动态规划专题精讲》,读者不仅能提升对动态规划的理解,还能在解决问题的过程中培养出强大的算法思维。无论是在面试还是实际工作中,动态规划都是程序员必须掌握的重要技能之一。因此,这份PDF是程序员们不可多得的学习资源,值得投入时间去研读和实践。
资源详情
资源推荐
3. dp数组如何初始化
在回顾⼀下dp[i]的定义:爬到第i层楼梯,有dp[i]中⽅法。
那么i为0,dp[i]应该是多少呢,这个可以有很多解释,但都基本是直接奔着答案去解释的。
例如强⾏安慰⾃⼰爬到第0层,也有⼀种⽅法,什么都不做也就是⼀种⽅法即:dp[0] = 1,
相当于直接站在楼顶。
但总有点牵强的成分。
那还这么理解呢:我就认为跑到第0层,⽅法就是0啊,⼀步只能⾛⼀个台阶或者两个台
阶,然⽽楼层是0,直接站楼顶上了,就是不⽤⽅法,dp[0]就应该是0.
其实这么争论下去没有意义,⼤部分解释说dp[0]应该为1的理由其实是因为dp[0]=1的话在
递推的过程中i从2开始遍历本题就能过,然后就往结果上靠去解释dp[0] = 1。
从dp数组定义的⾓度上来说,dp[0] = 0 也能说得通。
需要注意的是:题⽬中说了n是⼀个正整数,题⽬根本就没说n有为0的情况。
所以本题其实就不应该讨论dp[0]的初始化!
我相信dp[1] = 1,dp[2] = 2,这个初始化⼤家应该都没有争议的。
所以我的原则是:不考虑dp[0]如果初始化,只初始化dp[1] = 1,dp[2] = 2,然后从i = 3开始
递推,这样才符合dp[i]的定义。
4. 确定遍历顺序
从递推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出,遍历顺序⼀定是从前向后遍历的
5. 举例推导dp数组
举例当n为5的时候,dp table(dp数组)应该是这样的
如果代码出问题了,就把dp table 打印出来,看看究竟是不是和⾃⼰推导的⼀样。
此时⼤家应该发现了,这不就是斐波那契数列么!
唯⼀的区别是,没有讨论dp[0]应该是什么,因为dp[0]在本题没有意义!
以上五部分析完之后,C++代码如下:
// 版本⼀
class Solution {
public:
int climbStairs(int n) {
if (n <= 1) return n; // 因为下⾯直接对dp[2]操作了,防⽌空指针
vector<int> dp(n + 1);
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) { // 注意i是从3开始的
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
};
时间复杂度:$O(n)$
空间复杂度:$O(n)$
当然依然也可以,优化⼀下空间复杂度,代码如下:
时间复杂度:$O(n)$
空间复杂度:$O(1)$
后⾯将讲解的很多动规的题⽬其实都是当前状态依赖前两个,或者前三个状态,都可以做空
间上的优化,但我个⼈认为⾯试中能写出版本⼀就够了哈,清晰明了,如果⾯试官要求进⼀
步优化空间的话,我们再去优化。
因为版本⼀才能体现出动规的思想精髓,递推的状态变化。
拓展
这道题⽬还可以继续深化,就是⼀步⼀个台阶,两个台阶,三个台阶,直到 m个台阶,有
多少种⽅法爬到n阶楼顶。
// 版本⼆
class Solution {
public:
int climbStairs(int n) {
if (n <= 1) return n;
int dp[3];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
int sum = dp[1] + dp[2];
dp[1] = dp[2];
dp[2] = sum;
}
return dp[2];
}
};
这又有难度了,这其实是⼀个完全背包问题,但⼒扣上没有这种题⽬,所以后续我在讲解背
包问题的时候,今天这道题还会拿从背包问题的⾓度上来再讲⼀遍。
这⾥我先给出我的实现代码:
代码中m表⽰最多可以爬m个台阶。
以上代码不能运⾏哈,我主要是为了体现只要把m换成2,粘过去,就可以AC爬楼梯这道
题,不信你就粘⼀下试试,哈哈。
此时我就发现⼀个绝佳的⼤⼚⾯试题,第⼀道题就是单纯的爬楼梯,然后看候选⼈的代码实
现,如果把dp[0]的定义成1了,就可以发难了,为什么dp[0]⼀定要初始化为1,此时可能候
选⼈就要强⾏给dp[0]应该是1找各种理由。那这就是⼀个考察点了,对dp[i]的定义理解的不
深⼊。
然后可以继续发难,如果⼀步⼀个台阶,两个台阶,三个台阶,直到 m个台阶,有多少种
⽅法爬到n阶楼顶。这道题⽬leetcode上并没有原题,绝对是考察候选⼈算法能⼒的绝佳好
题。
这⼀连套问下来,候选⼈算法能⼒如何,⾯试官⼼⾥就有数了。
其实⼤⼚⾯试最喜欢问题的就是这种简单题,然后慢慢变化,在⼩细节上考察候选⼈。
class Solution {
public:
int climbStairs(int n) {
vector<int> dp(n + 1, 0);
dp[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) { // 把m换成2,就可以AC爬楼梯这
道题
if (i - j >= 0) dp[i] += dp[i - j];
}
}
return dp[n];
}
};
总结
这道题⽬和动态规划:斐波那契数题⽬基本是⼀样的,但是会发现本题相⽐动态规划:斐波
那契数难多了,为什么呢?
关键是 动态规划:斐波那契数 题⽬描述就已经把动规五部曲⾥的递归公式和如何初始化都
给出来了,剩下⼏部曲也⾃然⽽然的推出来了。
⽽本题,就需要逐个分析了,⼤家现在应该初步感受出关于动态规划,你该了解这些!⾥给
出的动规五部曲了。
简单题是⽤来掌握⽅法论的,例如昨天斐波那契的题⽬够简单了吧,但昨天和今天可以使⽤
⼀套⽅法分析出来的,这就是⽅法论!
所以不要轻视简单题,那种凭感觉就刷过去了,其实和没掌握区别不⼤,只有掌握⽅法论并
说清⼀⼆三,才能触类旁通,举⼀反三哈!
使⽤最⼩花费爬楼梯
746. 使⽤最⼩花费爬楼梯
题⽬链接:https://leetcode-cn.com/problems/min-cost-climbing-stairs/
数组的每个下标作为⼀个阶梯,第 i 个阶梯对应着⼀个⾮负数的体⼒花费值 cost[i](下标从
0 开始)。
每当你爬上⼀个阶梯你都要花费对应的体⼒值,⼀旦⽀付了相应的体⼒值,你就可以选择向
上爬⼀个阶梯或者爬两个阶梯。
请你找出达到楼层顶部的最低花费。在开始时,你可以选择从下标为 0 或 1 的元素作为初
始阶梯。
剩余271页未读,继续阅读
icwx_7550592
- 粉丝: 20
- 资源: 7163
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 前端面试必问:真实项目经验大揭秘
- 永磁同步电机二阶自抗扰神经网络控制技术与实践
- 基于HAL库的LoRa通讯与SHT30温湿度测量项目
- avaWeb-mast推荐系统开发实战指南
- 慧鱼SolidWorks零件模型库:设计与创新的强大工具
- MATLAB实现稀疏傅里叶变换(SFFT)代码及测试
- ChatGPT联网模式亮相,体验智能压缩技术.zip
- 掌握进程保护的HOOK API技术
- 基于.Net的日用品网站开发:设计、实现与分析
- MyBatis-Spring 1.3.2版本下载指南
- 开源全能媒体播放器:小戴媒体播放器2 5.1-3
- 华为eNSP参考文档:DHCP与VRP操作指南
- SpringMyBatis实现疫苗接种预约系统
- VHDL实现倒车雷达系统源码免费提供
- 掌握软件测评师考试要点:历年真题解析
- 轻松下载微信视频号内容的新工具介绍
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功