动态规划总结篇
代码地址https://github.com/Ltd5552/Algorithm/tree/master/8-DP
前面主要对动态规划的四类经典问题进行了分析解决，这里再进行一次总结归纳，以便加深印象。
- 背包问题
- 打家劫舍
- 股票买卖
- 子序列
背包问题
背包问题主要细分为01背包和完全背包（当然还有非常多类型），唯一的差别在于物品是否能多次使用，而该类问题的关键是确定遍历的顺序。
对于01背包，开始引入了dp数组维度的降低，主要的能降维的原因就是一些问题在递推的时候只会依赖上一层的数据，这就可以使用滚动数组不断复用空间。但同时，因为上一层的数据无法持久保存，为了不在使用前就被覆盖了所以是倒序遍历的容量，而且只能先遍历物品再遍历容量。
对于完全背包，引入了排列组合，不同的遍历顺序将导致不同的结果。如果是求装满背包有多少种方式，递推公式都是一样的，递推公式则有说法：
- 如果求组合数就是外层for循环遍历物品，内层for遍历背包。
- 如果求排列数就是外层for遍历背包，内层for循环遍历物品。
排列数是强调顺序的，组合数是顺序无关的，对于不同的问题求解的目标也不尽相同。
当然完全背包也不一定全是排列组合，也存在求最小数。
另一类不太常见的是多重背包，解决的办法就是将有限个物品全部分开作为单独一个物品，这样就转换为了01背包问题，按01背包问题的解法就行。
背包类型的问题大多需要对题意理解后转换，思考什么是物品什么是背包，迈出这一步后剩下的其实就和上面总结的非常相似了。
打家劫舍
打家劫舍问题并不多，而三道题各有特点，但核心是在状态转移上，即如何找到递推关系是非常重要的，因为打家劫舍一般都会借“报警”之口来进行限制状态的转移，如何确定正确的转移方式非常重要。
而且对于特殊的结构（比如第二道环形）不一定死磕状态，可以尝试将状态进行拆分隔离，而第三道引入树形dp，更加考察对二叉树遍历的熟悉程度，状态的转移其实和前两道差不多。
股票买卖
股票买卖同样主要考察对dp数组的定义和状态转移的分析，将状态细分后一一列出来，每一天的情况考虑完全。对于限制买卖次数无非就是增加了状态的分析，对于没法一一分析的看能否找到统一的规律，通过奇偶进行交错表示。
子序列
子序列问题也是dp的经典，可以细分为连续、不连续、编辑距离和回文四种。
首要的就是正确理解dp数组的定义，一些是以nums[i]结尾但最终结果并不一定是最后一个，因为最优解并不一定包含最后一个字符，比如最长递增子序列；而另一些是定义为[0, i]之间的最优值，那么结果就是越往后越优（因为是不断取max增加的过程），最优的结果就是dp数组的结束部分，比如最长公共子序列
连续的就是数组，状态转移就只依靠邻近的，不连续的就是真·序列，状态转移只要是前面的都有可能，选择的是全部可能性中最优的。
编辑距离的四道题是层层递进，逐步引入”编辑“的概念，开始可能不太理解删除的含义，后面才逐渐理解深入，其实就是”不考虑“，这里还需要注意初始化，如果一个串空，那么编辑次数显然就是把另一个串删完（也可以是添加完），这里引入爱因斯坦相对论，删除和增加是相对的，你删就等于他增，一删一增次数都一样所以可以合并。
最后是回文子串，借助左右指针的思路利用二维数组表示边界，特别注意递推的子问题来源，这完全影响了遍历的顺序问题。
总结
总而言之，遇到问题首要是看能不能动态规划，是否具有重叠子问题和最优子结构，不能强行就来动态规划。
思维框架如下
- 确定DP数组及下标的含义
- 确定递推公式
- 确定DP数组如何初始化
- 确定遍历顺序
- 举例推导DP数组
之前的题目其实很多第五步都没有提到过，唯一一次似乎就是最长递增子序列，其实这一步也非常重要，可以帮你更加具体地理解dp推导的过程，并让你清楚你写的是否合理正确。
dp的过程是一个不断试探最终找到最优解的过程，核心思想就是最简单的穷举法，理解了这一点你才会发现，dp的学习才刚刚开始。