什么是动态规划，我们如何描述？
动态编程算法通常基于一个递归公式和一个或多个初始状态。当前子问题的解将从前一个子问题的解推导出来。使用动态规划求解问题只需要多项式时间复杂度，因此比回溯法和暴力法快得多。首先需要找到某个状态的最优解，然后在它的帮助下找到下一个状态的最优解。
“状态”用来描述这个问题的子问题的解。
递归、递归和迭代
迭代算法是计算机解决问题的基本方法。它利用计算机的运算速度快，适合重复运算，使计算机可以重复执行一组指令(或某些步骤)，每次执行指令(或这些步骤)时，从原始值导出变量的新值。
一般来说，迭代俗称“循环”。在编程语言中，for\\\loop等都是循环
递归与循环：理论上所有的递归函数都可以转化为迭代函数，反之亦然，但是代价通常比较高。递归多了，内存占用也会增加。
递归和递归：
从程序的角度来说，递归表明你调用自己，但是递归没有这样的形式。
递归就是从问题的最终目的出发，逐渐把复杂的问题变成简单的问题，最后得到问题。反了。递归从一个简单的问题开始，一步一步发展，最后得到问题。是正面的。
在递归中，问题的n要求在计算前已知，而递归可以在计算中确定，不需要在计算前知道n。
一般来说递归比递归效率高(当然如果递归可以计算的话)。
动态规划和贪婪算法的区别
相同点
动态规划和贪婪算法都是递归算法。有局部最优解来导出全局最优解。
差异
贪婪算法：
在贪婪算法中，每一个贪婪决策都是不可改变的，因为贪婪策略是从上一个最优解推导出下一个最优解，而上一个最优解是不保留的。
从(1)中的介绍可以知道，贪心法的正确条件是每一步的最优解必须包含前一步的最优解。
动态编程算法：
全局最优解必须包含一个局部最优解，但不一定包含以前的局部最优解，所以需要记录所有以前的最优解
动态规划的关键是状态转移方程，即如何从局部最优解推导出全局最优解
边界条件：可以直接得到的最简单的局部最优解
贪心法的基本思路
从问题的某个初始解开始，我们逐渐逼近某个给定的目标，以尽快得到更好的解。当算法到达某一步时，算法停止。该算法存在问题：
不能保证最终的解决方案是最好的。
不能用来求最大值或最小值的解；
只能找到满足一定约束的可行解的范围。实现算法的过程：从问题的一个初始解开始；
能够朝着给定的总体目标更进一步
找到可行解的解元素；
问题的可行解由所有解元素组成。
贪婪算法最经典的例子
，给钱。比如中国的货币只看人民币，包括1元，2元，5元，10元20，50，100
如果我要16块钱，我可以拿16块1，8块2，但是怎么才能拿的最少？如果我用贪婪，我每次拿那个都会得到最大的。比如16，第一次拿不起20，拿10块，OK，然后6块，然后5块，然后1块，就是三个十，五，一。
贪婪是你每次能拿的最大的东西。
但必须注意的是，贪婪并没有得到最优解，也就是说贪婪不一定得到最少的张数，贪婪只能得到更好的解，贪婪算法非常容易得到。再注意一下，为什么我们的钱可以贪？因为我们国家的货币大小是设计好的，可以让贪婪算法计算出最优解(一般一个国家的硬币应该是这样设计的)。如果换个方式设计，情况就不一样了。
例如，公司
想拿6块钱，怎么拿？如果你很贪心，先拿四个，再拿两个，一共三块钱
实际最优呢？两个3块钱就够了。
寻找最优解的问题，从根本上说是对解空间的遍历。最直接的暴力分析很容易得到，最优解的解空间通常呈指数增长，所以暴力耗竭不可行。大多数最优解问题可以分为子问题。如果把解空间的遍历看成是子问题树的遍历，那么以某种形式遍历整棵树一次就可以得到最优解。如上分析，不可行。贪心和动态规划本质上都是修剪子问题树。两个算法要求问题的一个性质是“子问题最优性”。也就是说，构成最优解的每个子问题的解对于这个子问题本身来说肯定是最优的。如果从上到下看问题树(以原问题为根)，每次只需要遍历代表最优解的子树，就可以保证得到全局最优解。说白了，你可以简单的用一个值(最优值)来表示整个子树，而不是找出这个子树可能代表的所有值。动态规划法代表了这类问题的一般解法。我们从下到上(从叶到根)构造子问题的解。对于每一个子树的根，我们找到下面每一片叶子的值，把最好的值作为自己的值，丢弃其他的值。动态规划的成本取决于备选方案的数量(树叉数)和子问题的数量(树节点数，还是树高？)。贪心算法是动态规划方法的特例。贪心在于可以证明每个子树的根的值不依赖于下层叶子的值，只依赖于问题的现状。换句话说，您可以在不知道节点的所有子树的情况下找到该节点
的值。通常这个值都是对于当前的问题情况下，显而易见的“最优”情况。因此用“贪心”来描述这个算法的本质。由于贪心算法的这个特性，它对解空间树的遍历不需要自底向上，而只需要自根开始，选择最优的路，一直走到底就可以了。这样，与动态规划相比，它的代价只取决于子问题的数目，而选择数目总为1。动态规划：从新手到专家
意识到，DP是由上一个状态解找到下个状态解，所以一般要去找上一个状态，如
相关阅读
标签： #动态规划最新问题
