没有合适的资源?快使用搜索试试~ 我知道了~
「代码随想录」动态规划专题精讲(v2.0).pdf
需积分: 5 0 下载量 159 浏览量
2024-04-22
15:03:38
上传
评论
收藏 8.72MB PDF 举报
温馨提示
试读
272页
「代码随想录」动态规划专题精讲(v2.0)
资源推荐
资源详情
资源评论
「代码随想录」动态规划专题精讲
作者:程序员
Carl
关于代码随想录
代码随想录官⽹:www.programmercarl.com
代码随想录开源项⽬Github:https://github.com/youngyangyang04/leetcode-
master
代码随想录算法公开课 ,代码随想录的全部内容将由我(程序员Carl)视频讲解
并开免费开放给⼤家。
《代码随想录》纸质版 已经出版。
代码随想录知识星球 上万录友在这⾥学习
代码随想录算法训练营 帮助录友⾼效刷完代码随想录。
PDF背景
该pdf是公众号「代码随想录」动态规划专题的⽂章整理⽽来。
⽬前已经发布了,⼆叉树PDF、回溯算法PDF、贪⼼算法PDF、动态规划PDF,程序员求职
攻略PDF 都⼴受获评,⼤家可以关注微信公众号:代码随想录,后台回复:666,就可以获
取全部专题PDF了。
但⼤家都知道算法⾥的桂冠是动态规划,⽆论是学习还是⾯试,动态规划都是最重要的。所
以这本动态规划PDF备受期待,那么Carl也不会让⼤家们失望!
这次发布的动态规划PDF共8万字,50多张分析图,50篇精品⽂章,共200页!,详细讲解
了40多道⼒扣(Leetcode)动态规划经典题⽬
依旧保持「代码随想录」严谨缜密的风格,这是全⽹对动规最深刻的讲解系列了。
其实⼤家去⽹上搜⼀搜也可以发现,能把动态规划讲清楚的资料挺少的,因为动规确实很
难!要给别⼈讲清楚更难!
《剑指offer》上 动规的题⽬很少,属于蜻蜓点⽔,很多细节都没有讲透彻,经典的算法书
籍《算法4》 没有讲 动规,⽽《算法导论》讲的动规基本属于劝退级别的。
讲清楚⼀道题容易,讲清楚两道题也容易,但把整个动态规划的各个分⽀讲清楚,每道题⽬
讲通透,并⽤⼀套⽅法论把整个动规贯彻始终就⾮常难了。
所以Carl花费的这么⼤精⼒,把⾃⼰对动规算法理解 ⼀五⼀⼗的全部分享出来,帮助⼤家
少⾛弯路!
相信只要⼤家认真学完这本PDF,不会让你失望的!!
本PDF统⼀使⽤C++进⾏讲解,对于使⽤其他语⾔的同学,也不会影响⼤家对算法思维的理
解。
代码随想录刷题⽹站已经上线了:www.programmercarl.com,同时⽀持C++、Java,
Python,Go,JavaScript版本,去看看吧,⼀个只要你发现 就会收藏的硬核算法学习⽹
站!
Github同步:https://github.com/youngyangyang04/leetcode-master
同时我也在B站上讲解算法,点击这⾥直达B站。
PDF难免会有笔误,或者⼩问题,所以内容会不断进⾏修正,其更新顺序为:Github > 公众
号 > ⽹站 > PDF。最新版本的PDF会⾸先在公众号⾥发布,不要错过咯。
那么如何使⽤这本PDF?
就是按顺序刷就可以了!
题⽬顺序都编排好了,按照pdf⾥排好的题⽬顺序来刷效果最好,这份刷题顺序已经陪伴上
万录友(代码随想录的朋友们)。
本PDF题⽬⼤纲如下:
做动规题⽬的时候,很多同学会陷⼊⼀个误区,就是以为把状态转移公式背下来,照葫芦画
瓢改改,就开始写代码,甚⾄把题⽬AC之后,都不太清楚dp[i]表⽰的是什么。
这就是⼀种朦胧的状态,然后就把题给过了,遇到稍稍难⼀点的,可能直接就不会了,然后
看题解,然后继续照葫芦画瓢陷⼊这种恶性循环中。
状态转移公式(递推公式)是很重要,但动规不仅仅只有递推公式。
对于动态规划问题,我将拆解为如下五步曲,这五步都搞清楚了,才能说把动态规划真的掌
握了!
1. 确定dp数组(dp table)以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组
动规专题刚开始的时候,讲的题⽬⽐较简单,不少录友和我反应:这么简单的题⽬ 讲的复
杂了,不⽤那么多步骤分析,想出递推公式直接就AC这道题⽬了。
Carl的观点⼀直都是 简单题是⽤来 巩固⽅法论的。 简单题⽬是可以靠感觉,但后⾯稍稍难
⼀点的题⽬,估计感觉就不好使了。
在动规专题讲解中,也充分体现出,这动规五部曲的重要性。
还有不少录友对动规的理解是:递推公式是才是最难最重要的,只要想出递归公式,其他都
好办。
其实这么想的同学基本对动规理解的不到位的。
动规五部曲⾥,哪⼀部没想清楚,这道题⽬基本就做不出来,即使做出来了也没有想清楚,
⽽是朦朦胧胧的就把题⽬过了。
如果想不清楚dp数组的具体含义,递归公式从何谈起,甚⾄初始化的时候就写错
了。
例如动态规划:不同路径还不够,要有障碍! 在这道题⽬中,初始化才是重头戏
如果看过背包系列,特别是0-1背包,完全背包,那么两层for循环先后顺序绝对可
以搞懵很多⼈,反⽽递归公式是简单的。
⾄于推导dp数组的重要性,动规专题⾥⼏乎每篇Carl都反复强调,当程序结果不对
的时候,⼀定要⾃⼰推导公式,看看和程序打印的⽇志是否⼀样。
动态规划理论基础
什么是动态规划
动态规划,英⽂:Dynamic Programming,简称DP,如果某⼀问题有很多重叠⼦问题,使
⽤动态规划是最有效的。
所以动态规划中每⼀个状态⼀定是由上⼀个状态推导出来的,这⼀点就区分于贪⼼,贪⼼没
有状态推导,⽽是从局部直接选最优的,
在关于贪⼼算法,你该了解这些!中我举了⼀个背包问题的例⼦。
例如:有N件物品和⼀个最多能背重量为W 的背包。第i件物品的重量是weight[i],得到的
价值是value[i] 。每件物品只能⽤⼀次,求解将哪些物品装⼊背包⾥物品价值总和最⼤。
动态规划中dp[j]是由dp[j-weight[i]]推导出来的,然后取max(dp[j], dp[j - weight[i]] +
value[i])。
但如果是贪⼼呢,每次拿物品选⼀个最⼤的或者最⼩的就完事了,和上⼀个状态没有关系。
剩余271页未读,继续阅读
资源评论
zh_19995
- 粉丝: 80
- 资源: 7
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功