概述
什么是动态规划
动态规划，英⽂：
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
背包的问题，那么就需要在把对应的理论知识讲解⼀下。
⼤家会发现，我讲解的理论基础并不是教科书上各种动态规划的定义，错综复杂的公式。
最后
以上就是开朗早晨为你收集整理的动态规划详解的全部内容，希望文章能够帮你解决动态规划详解所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复