leetcode动态规划算法详细讲解_动态规划算法资源-CSDN文库

leetcode

动态规划

需积分: 5 173 浏览量 2023-08-29 15:38:03 上传评论 1 收藏 9.02MB PDF 举报

资源推荐

资源详情

资源评论

《代码随想录》作者：程序员Carl

代码随想录官⽹（网站持续更新优化内容，建议直接看网站）：www.programmercarl.com

代码随想录Github开源地址

代码随想录算法公开课，代码随想录的全部内容将由我（程序员Carl）视频讲解并开免费开放给⼤家。

《代码随想录》已经出版。

代码随想录知识星球上万录友在这⾥学习

代码随想录算法训练营帮助录友⾼效刷完代码随想录。

微信公众号：代码随想录

组队刷题，可以添加代码随想录官⽅微信

ACM模式练习，推荐：卡码⽹

特别提示：PDF仅提供C++语⾔版本同时PDF中很多动图⽆法加载，其他编程语⾔版本和查看动图可以移步⾄代码

随想录官⽅⽹站查看。

1. 动态规划理论基础

动态规划刷题⼤纲

算法公开课

《代码随想录》算法视频公开课：动态规划理论基础，相信结合视频再看本篇题解，更有助于⼤家对本题的理解。

什么是动态规划

动态规划，英⽂：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])。

但如果是贪⼼呢，每次拿物品选⼀个最⼤的或者最⼩的就完事了，和上⼀个状态没有关系。

所以贪⼼解决不了动态规划的问题。

其实⼤家也不⽤死扣动规和贪⼼的理论区别，后⾯做做题⽬⾃然就知道了。

⽽且很多讲解动态规划的⽂章都会讲最优⼦结构啊和重叠⼦问题啊这些，这些东⻄都是教科书的上定义，晦涩难懂

⽽且不实⽤。

⼤家知道动规是由前⼀个状态推导出来的，⽽贪⼼是局部直接选最优的，对于刷题来说就够⽤了。

上述提到的背包问题，后序会详细讲解。

动态规划的解题步骤

做动规题⽬的时候，很多同学会陷⼊⼀个误区，就是以为把状态转移公式背下来，照葫芦画瓢改改，就开始写代

码，甚⾄把题⽬AC之后，都不太清楚dp[i]表示的是什么。

这就是⼀种朦胧的状态，然后就把题给过了，遇到稍稍难⼀点的，可能直接就不会了，然后看题解，然后继续照葫

芦画瓢陷⼊这种恶性循环中。

状态转移公式（递推公式）是很重要，但动规不仅仅只有递推公式。

对于动态规划问题，我将拆解为如下五步曲，这五步都搞清楚了，才能说把动态规划真的掌握了！

1. 确定dp数组（dp table）以及下标的含义

2. 确定递推公式

3. dp数组如何初始化

4. 确定遍历顺序

5. 举例推导dp数组

⼀些同学可能想为什么要先确定递推公式，然后在考虑初始化呢？

因为⼀些情况是递推公式决定了dp数组要如何初始化！

后⾯的讲解中我都是围绕着这五点来进⾏讲解。

可能刷过动态规划题⽬的同学可能都知道递推公式的重要性，感觉确定了递推公式这道题⽬就解出来了。

其实确定递推公式仅仅是解题⾥的⼀步⽽已！

⼀些同学知道递推公式，但搞不清楚dp数组应该如何初始化，或者正确的遍历顺序，以⾄于记下来公式，但写的程

序怎么改都通过不了。

后序的讲解的⼤家就会慢慢感受到这五步的重要性了。

动态规划应该如何debug

相信动规的题⽬，很⼤部分同学都是这样做的。

看⼀下题解，感觉看懂了，然后照葫芦画瓢，如果能正好画对了，万事⼤吉，⼀旦要是没通过，就怎么改都通过不

了，对 dp数组的初始化，递推公式，遍历顺序，处于⼀种⿊盒的理解状态。

写动规题⽬，代码出问题很正常！

找问题的最好⽅式就是把dp数组打印出来，看看究竟是不是按照⾃⼰思路推导的！

⼀些同学对于dp的学习是⿊盒的状态，就是不清楚dp数组的含义，不懂为什么这么初始化，递推公式背下来了，

遍历顺序靠习惯就是这么写的，然后⼀⿎作⽓写出代码，如果代码能通过万事⼤吉，通过不了的话就凭感觉改⼀

改。

这是⼀个很不好的习惯！

做动规的题⽬，写代码之前⼀定要把状态转移在dp数组的上具体情况模拟⼀遍，⼼中有数，确定最后推出的是想要

的结果。

然后再写代码，如果代码没通过就打印dp数组，看看是不是和⾃⼰预先推导的哪⾥不⼀样。

如果打印出来和⾃⼰预先模拟推导是⼀样的，那么就是⾃⼰的递归公式、初始化或者遍历顺序有问题了。

如果和⾃⼰预先模拟推导的不⼀样，那么就是代码实现细节有问题。

这样才是⼀个完整的思考过程，⽽不是⼀旦代码出问题，就毫⽆头绪的东改改⻄改改，最后过不了，或者说是稀⾥

糊涂的过了。

这也是我为什么在动规五步曲⾥强调推导dp数组的重要性。

举个例⼦哈：在「代码随想录」刷题⼩分队微信群⾥，⼀些录友可能代码通过不了，会把代码抛到讨论群⾥问：我

这⾥代码都已经和题解⼀模⼀样了，为什么通过不了呢？

发出这样的问题之前，其实可以⾃⼰先思考这三个问题：

这道题⽬我举例推导状态转移公式了么？

我打印dp数组的⽇志了么？

打印出来了dp数组和我想的⼀样么？

如果这灵魂三问⾃⼰都做到了，基本上这道题⽬也就解决了，或者更清晰的知道⾃⼰究竟是哪⼀点不明⽩，是状态

转移不明⽩，还是实现代码不知道该怎么写，还是不理解遍历dp数组的顺序。

然后在问问题，⽬的性就很强了，群⾥的⼩伙伴也可以快速知道提问者的疑惑了。

注意这⾥不是说不让⼤家问问题哈，⽽是说问问题之前要有⾃⼰的思考，问题要问到点⼦上！

⼤家⼯作之后就会发现，特别是⼤⼚，问问题是⼀个专业活，是的，问问题也要体现出专业！

如果问同事很不专业的问题，同事们会懒的回答，领导也会认为你缺乏思考能⼒，这对职场发展是很不利的。

所以⼤家在刷题的时候，就锻炼⾃⼰养成专业提问的好习惯。

总结

这⼀篇是动态规划的整体概述，讲解了什么是动态规划，动态规划的解题步骤，以及如何debug。

动态规划是⼀个很⼤的领域，今天这⼀篇讲解的内容是整个动态规划系列中都会使⽤到的⼀些理论基础。

在后序讲解中针对某⼀具体问题，还会讲解其对应的理论基础，例如背包问题中的01背包，leetcode上的题⽬都是

01背包的应⽤，⽽没有纯01背包的问题，那么就需要在把对应的理论知识讲解⼀下。

⼤家会发现，我讲解的理论基础并不是教科书上各种动态规划的定义，错综复杂的公式。

这⾥理论基础篇已经是⾮常偏实⽤的了，每个知识点都是在解题实战中⾮常有⽤的内容，⼤家要重视起来哈。

今天我们开始新的征程了，你准备好了么？

2. 斐波那契数

⼒扣题⽬链接

斐波那契数，通常⽤!F(n) 表示，形成的序列称为斐波那契数列。该数列由!0 和 1 开始，后⾯的每⼀项数字都是前

⾯两项数字的和。也就是：

F(0) = 0，F(1)!= 1

F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给你n ，请计算 F(n) 。

示例 1：

输⼊：2

输出：1

解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

输⼊：3

输出：2

解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

剩余232页未读，继续阅读

评论收藏

内容反馈

haven-852

粉丝: 992
资源: 23

leetcode动态规划算法详细讲解

leetcode

LeetCode

动态规划算法笔记总结ZIP分享

leetcode算法题主函数如何写-Dynamic-Programming-Note:动态规划算法学习心得（leetcode)

LeetCode 刷题攻略：配思维导图，100+经典算法题目刷题顺序、经典算法模板-Python开发

leetcode-master:LeetCode刷题攻略：配思维导图，100 +经典算法译文刷题顺序，经典算法模板，共40w字的详细图解，以及难点视频题解。学习上不再迷茫！:fire::fire:给个star支持一下吧！:rocket:

leetcode题库-LeetCode-Topic:LeetCode专题刷题模板分类Java版讲解

leetcode和oj-Dynamic-Programming-9C:九章算法动态规划专题相关代码

leetcode下载-leetcode-01:leetcode-01

leetcode答案-dailyLeetCode:每日LeetCode

leetcode题库-hello-offer:图解剑指Offer，迎接秋招，找到好工作

leetcode凑硬币-Arithmatic:算术

leetcode2-IntroductionToOI:软院科协兴趣小组-OI小组

模式问题汇总：基于用于解决问题的技术的相似性，我对算法问题的模式进行了总结，并提供了详细的初学者友好型数据结构和算法教程

cpp-算法精粹

youngyangyang04

lrucacheleetcode-Algorithms-and-data-structures:算法与数据结构等-知识荟萃「长期更新中」【欢迎

Java第十五届蓝桥杯大赛软件JavaB组真题

SwitchHosts

安卓期末大作业（AndroidStudio开发），垃圾分类助手app，分为前台后台，代码有注释，均能正常运行

Notepad++安装包

2024北森能力测评题库.7z

微信小程序源码-合集1.rar

Java面试八股文2023最新版

Linux Centos7 升级最新版OpenSSH-9.6p1 有脚本（支持离线）

JDK1.8 windows 64位

ruoyi-vue-pro 芋道源码项目的表结构

ruoyi-vue-pro开发指南PDF下载

myeclipse 10.7.1 windows 安装包

最新资源