前言
以前虽然知道动态规划，但是对于它的理解仅仅停留于背“状态转移方程”的阶段，随着我的理解和深入，我对这个问题有了更多的思考。
首先我的一个感受是，如果上来就去掌握状态转移方程，无后效性等、状态压缩及倒序循环、初始化等概念是不合适的，例如在某些"X分钟学算法"中告诉你求解动态规划很简单只需要四步1.问题拆解；2. 状态定义 3.递归方程推导 4. 实现…对于一个刚刚接触到动态规划的新手来说，这种教程是很不负责任的。
这种”总结“看似帮助初学者掌握了动态规划的方法，但是实际上却仍只是浅浅的一层缺乏深入理解，此外对于动态规划中最关键的部分”状态转移方程推导“仍会使得很多新手望而却步。我自己也走过这些弯路，但是在无数次磕磕绊绊中，我对动态规划的认知之间加深，这篇一篇文章也是自己对于动态规划这个坑的小总结，同时也希望后来人不要再步入我的”磕磕绊绊“后尘，要想理解动态规划首先要从搜索和记忆化搜索讲起，因为动态规划的本质是记忆化搜索。
动态规划的本质是记忆化搜索
此外，如果没有重复子问题，动态规划往往会退化为搜索（暴力穷举），很多人认为“使用了动态规划就一定会降低时间复杂度“，其实并不是这样的。动态规划能够起到优化作用的前提条件是：具备重复子问题结构。
以Leetcode 91题解码方法为例，对于一个字符串 F("2213")=5, 可以分解为 F("213")和 F("13")两个子问题，在 F("213")这个子问题中又可以分为 F("13")和 F("3")两个子子问题，F("13")这个子子问题和 F("13")子问题是重复的，因而可以考虑使用记忆化搜索或动态规划来解决这个问题。同样地，动态规划也并非能够对所有的问题产生”记忆化“的作用：
以Leetcode 91题解码方法为例，如果一个数中的一个前缀和两个前缀都是合法的，那么这个值就等同于斐波那契数列+1（，例如f("12121212")=Fibonaccic number(8+1) = 34 此时动态规划也就没有了意义（此时遍历了所有的解空间）
以Leetcode 322题零钱兑换为例，倘若硬币组合是[2,4,8,16], 16, 则此时动态规划此时同样也没有起到优化的作用，因为在这该问题下，不具有重复的子结构（此时不存在重叠的子问题）
这也从侧面说明了，所有的动态规划，都能够通过DFS+记忆化搜索来实现，实际上记忆化搜索由于更加符合人的直觉，在某些问题上往往能够写出更加高效、易读的代码。
以Leetcode 72题编辑距离为例，使用记忆化搜索很容易就能够把状态转移的关系表示出来，进而写出高效易读的代码。
最后总结一下，动态规划所有循环求解的问题都可以使用DFS深搜来解决，且只需要引入一个数组用来记录子问题的值（记忆化搜索）就能够达到和循环求解一样的时间复杂度。当然这句话说得有些绝对，需要结合主定理来做进一步的分析，在由于某些语言中由于栈容量的限制N不能过大，但是倘若还能够使用合适的剪枝策略，记忆化搜索甚至还会超过循环求解（e.g. Leetcode 322零钱兑换）所以我们可以说：掌握了搜索就掌握了动态规划！
多状态
在一个问题中，往往具有多个状态，这些不同状态之间存在相互作用转化的关系，此时应该应该针对不同的状态开辟不同的数组。
以Leetcode 121买卖股票的最佳时机为例，包含了两种状态：一种是当前状态下股票的最低价格，一种是当前状态下股票卖掉时能够获取到的最大利润。
以Leetcode 309买卖股票的最佳时机含冷冻期为例，这里面包含了三个状态，需要我们梳理好这三个状态之间的关系。
针对多状态问题，只要我们好好体会不同状态之间的转化关系，绘制好状态转移图，根据状态转移图整理好不同状态之间的状态转移方程，就能够解决这类问题。
空间压缩（滚动数组）
由于某些动态转移方程所具有的性质，往往可以将空间复杂度降低一个时间复杂度级别。
以Leetcode 198打家劫舍 为例，在该题目中，该题的状态转移方程为F[i] = max(F[i-1], F[i-2] + num[i]),根据状态转移方程可以得知，当前的状态仅由前一个状态和前两个状态有关，那么对于这个状态转移方程，我们只需要准备两个变量用来保存前一个状态和前两个状态的值，再利用辅助变量将问题的空间复杂度由之前的O(n)降低到O(1)。
以Leetcode 322零钱兑换为例，零钱兑换（这道题和背包问题有相似之处)的状态转移方程是F[i][j] = max(F[i-1][j], F[i-1][j-coins[i]] + 1,如果根据这道题的状态转移方程来申请dp数组的话，我们应该选取的是M*N的二维数组，其中M是硬币的面值数，N是当前求得金额的值。从状态转移方程中，我们同样可以发现F[i][j]的值都是由F[i-1][*]也就是上一层的状态所决定。那么基于这个观察，我们就可以将空间复杂度从O(N^2)压缩到O(N)。
在某些情况下，为了避免F[i-1]被提前更新，需要将部分循环倒序处理。
倒序处理利用的是动态规划的无后效性，当然技巧与算法没有关系，只是帮助我们写出更加”巧妙“的代码。除了循环倒序处理以外，简单地，我们还可以额外引入一个数组临时，用来存储上一轮N-1循环的变量，然后在下一轮循环N后，再将第N论计算的数组覆盖到N-1临时数组上以备第N+1轮使用，如此反复……，这个技巧就是滚动数组。
最后，空间压缩在某些问题无法使用，例如在LCS最长公共子序列等问题中不能降低空间复杂度。
以Leetcode 322 零钱兑换为例，如果规定了每个硬币数目是无限的，那么我们的解决方案就是将原有的倒序循环改成正序循环。
以Leetcode 518 零钱兑换II为例，如果规定了每个硬币数目是无限的，且要求计算找零的方案数（而不是最小硬币数）,则此处不仅仅要正序处理，而且要修改状态转移方程为F[i] = F[j] + dp[j-coin]，此时该问题变成了一个递推问题。
坑1：初始化
对于动态规划，初始化的方式往往是一个坑，由于不同的题型往往会有不同的处理方式。虽然处理方式千奇百怪，但是在无数次的挣扎中，我也摸索出来了一些经验，我的经验是：如果当什么都不做的情况下，dp数组中每个解都是合法的，那么dp数组往往会初始化成0，如果当什么都不做的情况下，dp数组中每个解都是非法的，那么dp数组往往会初始化为INT_MAX或INT_MIN（视状态转移方程决定）
以0-1背包问题为例，如果最终题目要求可以不装满，那么则dp数组则初始化为0。如果要求恰好装满，那么此时只有容量为0的背包可以在什么都不装且截止为0的情况下被”恰好装满“，其他容量的背包没有合法的解，属于不合法的状态，因此要赋值为INT_MIN;如果要求背包并非被装满，那么任何容量的背包都存在一个合法的解”什么都不装“，这个合法的解对应的价值为0，所以初始状态的值也就是0了。
坑2：Padding
Padding是在动态规划循环求解中，为了避免对特例的处理保持循环的连续性（这一点和”Guard“(哨兵)的思想也是类似的，避免过多的条件判断）而引入的额外空间。
例如在背包问题中，对于dp[0]表示背包状态为0时的最大价值，我们知道完全背包问题的状态转移方程是F[i][j] = max(F[i-1][j], F[i-1][j- thisWeight] + thisValue), 如果不设置Padding的话，那么当j=1时，会引发越界异常,因而我们为0号元素分配一个空间以避免边界条件的处理。
对于Padding的初始化与坑1中的初始化是类似的，都有从实际问题出发，如果解是合法的，则初始化为0；如果不合法，则初始化为INT_MAX或INT_MIN