👺动态规划定义
动态规划在寻找有很多重叠子问题的情况的最佳解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并被储存，从简单的问题直到整个问题都被解决。因此，动态规划储存递迴时的结果，因而不会在解决同样的问题时花费时间。
🤡动态规划歪解
我们先计算1+1+1+1+1+1+1+1+1+1等于多少。通过计算，我们可以知道上面那个式子等于10，如果我们在上面那个式子的左边再加上一个1+呢？我们不用用手计算就可以直接知道等于11.因为我们知道了 1+上面那个式子 而这个结构中，那个式子结果等于10，我们记忆住了，避免了重复计算。这就是动态规划。
🧑动态规划步骤
建立状态转移方程（最难也是最重要的一步）
缓存并复用以往结果
按顺序从小往大算（自底向上）
🥶个人理解
总结来说，动态规划具有最优子结构和重叠子问题的特点， 动态规划的问题一般都和递归有相关性，并且动态规划能够优化递归，减少重复的计算量。也就是递归+备忘录记录值的效果。
从另一个角度来看，其实可以说每一个动态规划问题都可以用递归来解决，因为动态规划是递归的一种优化，削减了对于同一个子问题的重复计算所浪费的时间。
《剑指offer》中有句话总结的好：通常应用动态规划解决问题时，我们都是用递归的思路来分析问题的。
🐶贪心算法与动态规划
贪心算法着眼于当前阶段的最优解，并且期望这样下来得到的结果是全局的最优解（实际上未必是）。相比于动态规划有一定的固定模式来说，贪心更偏向是一种思想。
动态规划是计算了所有子问题的最优解，在最后通过上层来直接获取全局最优解。即动态规划在计算子问题时是没有偏好的，它会计算所有的子问题。而贪心算法，因为贪心，同样的子问题他只会计算最大（优）的一个。
贪心算法是每一步只选最优的，并且期望每一步选择的最优解能达成全局的最优解，说实话这太难了，因为一般一个问题的选择都会影响下一个问题的选择，除非子问题之间完全独立，没有关联，比如凑零钱的例子， 如果一个国家的钞票比较奇葩，只有 1，5，11 这三种面值的钞票，如何用最少的钞票凑出 15 呢，如果用贪心第一次选 11， 那之后只能选 4 张 1 了，即 15 = 1 x 11 + 4 x1。其实最优解应该是 3 张 5 元的钞票，为啥这种情况下用贪心不适用呢，因为第一次选了 11，影响了后面钞票的选择，也就是说子问题之间并不是独立的，而是互相制约，互有影响的，所以我们选贪心的时候一定要注意它的适用场景。
