没有合适的资源？快使用搜索试试~ 我知道了~

首页程序员Carl深度解析：动态规划专题PDF（v2.0）- 8万字详解40+LeetCode难题

程序员Carl深度解析：动态规划专题PDF（v2.0）- 8万字详解40+LeetCode难题

需积分: 5 0 下载量 123 浏览量更新于2024-06-13 收藏 8.72MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

试读

272页

"「代码随想录」动态规划专题精讲（v2.0）是由程序员Carl编撰的一份深入讲解动态规划的高质量资源。这本PDF共计8万字，包含50多张详细的分析图和50篇精选文章，覆盖200页内容，旨在帮助读者理解和掌握动态规划这一核心算法。动态规划在算法领域具有重要地位，无论是学习还是求职面试，它都是不可或缺的一部分。动态规划是算法中的明珠，但因其复杂性，网上的清晰讲解资料相对较少。例如，《剑指offer》虽然涉及动态规划，但深度不足；而经典教材如《算法4》和《算法导论》在动态规划部分的教学可能并不适合初学者。Carl为了弥补这些空白，投入大量精力，确保他的讲解严谨且透彻，力图帮助读者避免在学习过程中走弯路。本书特别强调使用C++进行讲解，同时考虑到不同编程语言的学习者，还提供了包括Java、Python、Go和JavaScript在内的多种语言版本的代码支持。代码随想录不仅提供了动态规划专题的PDF，还上线了刷题网站，支持多种编程语言，旨在打造一个全面且实用的算法学习平台。通过阅读这本PDF，学习者将有机会系统地学习40多道LeetCode的经典动态规划题目，深入了解动态规划的各个分支，以及一套连贯的方法论。这是一本致力于提升读者动态规划技能，帮助他们在算法领域取得突破的珍贵资源。只要读者投入时间和精力，相信都能从中收获满满。"

资源详情

资源推荐

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页未读，继续阅读

粉丝: 80
资源: 8

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

程序员Carl深度解析：动态规划专题PDF（v2.0）- 8万字详解40+LeetCode难题

动态规划专题精讲（v2.0）.pdf

动态规划专题.pdf

动态规划精讲

代码随想录知识星球精华-大厂面试八股文v1.1.pdf

代码随想录八股文pdf下载

代码随想录python

代码随想录知识星球精华pdf

代码随想录pdfcsdn

代码随想录 最强八股文pdf

代码随想录c++ webserver pdf

代码随想录 webserver pdf

代码随想录最强八股文pdf 第三版

牛客上代码随想录怎么看题刷题

代码随想录八股文第四版pdf

代码随想录知识星球精华|最强八股文pdf第四版 免费

代码随想录最强八股文

代码随想录 知识星球 八股文pdf

代码随想录算法训练营

代码随想录八股文第四版

代码随想录的python版本

最新资源

代码随想录最强八股文pdf

代码随想录知识星球精华|最强八股文pdf第四版免费

代码随想录知识星球八股文pdf