动态规划的理论基础什么是动态规划？因此，动态规划中的每个状态都必须从前一个状态派生而来。这与贪婪不同。Greedy没有状态推导，而是直接从局部中选择最好的。关于贪心算法你应该知道这个！我举了一个背包问题的例子。例如：有N件物品，一个最大重量为W的背包，第i件物品的重量为weight[i]，得到的值为value[i]。每个物品只能使用一次，找出总价值最大的物品放入背包。在动态规划中，dp[j]由dp[j-weight[i]]导出，然后取max(dp[j],dp[j-weight[i]]+value[i])。但是如果是贪心的，每次拿一个物品，选择最大或者最小的就完事了，跟之前的状态没有关系。所以贪心不能解决动态规划的问题。其实不用拘泥于移动规则和贪心的理论区别，后面做题自然就知道了。而且很多讲解动态规划的文章都会讲到最优子结构和重叠子问题。这些东西都是教科书中定义的，晦涩难懂，不切实际。大家都知道动态规则是从前一个状态推导出来的，贪心就是直接在局部选最好的，解题就可以了。上面提到的背包问题后面会详细解释。动态规划的解题步骤在做动态规划问题的时候，很多同学都会陷入一个误区，就是认为自己背了状态转移公式，照葫芦画瓢改，开始写代码，即使问题是空调，不是很好。清楚dp[i]代表什么。这是一种朦胧的状态，然后你过题，如果遇到稍微难一点的，可能马上做不出来，再看看题解，然后继续做跟着葫芦坠入这个怪圈。状态转移公式（递归公式）很重要，但运动规律不只是递归公式。对于动态规划问题，我将其拆解为以下五个步骤。只有弄清楚了这五个步骤，才能说我们真正掌握了动态规划！判断dp数组（dp表）和下标的含义及确定递归公式dp数组如何初始化及确定遍历顺序为例推导dp数组。可能有同学会疑惑，为什么要先确定递归公式，再考虑初始化呢？因为在某些情况下，递归公式决定了如何初始化dp数组！在后面的讲解中，我会重点用这五点来讲解。刷过动态规划题的同学可能知道递归公式的重要性，觉得递归公式确定后就可以解决递归公式的问题了。其实确定递归公式只是解题的第一步！有的同学知道递归公式，但是不知道怎么初始化dp数组，不知道正确的遍历顺序，以至于把公式写下来，但是不管怎么写程序，都改不了。不能通过。大家在后面的讲解中会逐渐感受到这五个步骤的重要性。动态规划调试应该如何相信动态规划？大多数学生都是这样做的。看了题解，感觉自己懂了，再依葫芦画瓢。如果你能画对，一切都会好起来的。一种黑盒状态的理解。代码在写动态规则的时候出现问题很正常！发现问题最好的方法就是把dp数组打印出来，看看是不是按照自己的思路推导的！有的同学对于dp学习处于黑盒状态，但是不清楚dp数组的含义，不明白为什么要这样初始化，递归公式背下来，遍历顺序这样写习惯，然后代码一口气写完，如果代码能通过就万事大吉，如果不行就凭感觉改。这是一个很不好的习惯！在写代码之前，一定要在写代码之前先模拟一下dp数组上状态转移的具体情况，这样才知道自己想要什么，确保最终的结果是自己想要的结果。然后写代码。如果代码失败，则打印dp数组，看看它是否与您预先推断的不同。如果打印出来的和你模拟前的推导一样，那么就是你自己的递归公式、初始化或者遍历顺序有问题。如果和你事先模拟推导的不一样，那就是代码实现的细节有问题。这是一个完整的思考过程，而不是一旦代码出了问题，就毫无头绪地东改西改，最后失败，或者糊涂过去。这就是为什么我在五步移动法则中强调推导dp数组的重要性。举个例子：在“代码乱录”团队的微信群里，有的录音师可能过不了代码，就把代码扔到讨论群里问：我这里的代码就是和题解一样，为什么我不能通过呢？什么？在问这样的问题之前，你其实可以自己想一下这三个问题：我有没有举个例子来推导这道题的状态转移公式？我是否打印了dp数组的日志？打印出来的dp数组和我想的一样吗？?如果灵魂三题都做了，基本上这个题就解决了，或者你会更清楚自己不懂的地方，不管是你不懂的状态转换，还是实现代码你不知道怎么写，或者不明白遍历dp数组的顺序。然后提问的时候目的性很强，群里的小伙伴也能??很快知道提问者的疑惑。注意，这里不是说大家不能提问，而是提问前一定要三思，提问要切中要害！工作之后，你会发现，尤其是在大厂，提问是一项专业的工作。是的，提问也应该表现出专业性！如果你问同事不专业的问题，同事会懒洋洋地回答，领导会认为你缺乏思考能力，这对职业发展是非常不利的。所以，大家在写题的时候，要锻炼自己，养成专业提问的好习惯。小结本文是对动态规划的整体概述，讲解什么是动态规划，动态规划的解题步骤，以及如何调试。动态规划是一个很大的领域。今天的讲解是整个动态规划系列都会用到的一些理论基础。在后序讲解中，针对一个具体的问题，也会讲解其相应的理论依据。比如背包问题中的01背包，leetcode上的题目都是01背包的应用，并没有纯粹的01背包问题，那么就需要讲解相应的理论知识。你会发现，我讲解的理论基础并不是教科书上各种动态规划的定义和错综复杂的公式。这里的理论基础已经很实用了。每个知识点在实战中解决问题都非常有用。每个人都应该注意它。
