一、动态规划演化
对于一个问题，如果我们能够将最大的问题，分解为几个子问题，然后通过选择连接大问题和子问题
然后子问题可以这样继续分解，那么，就意味着可以使用动态规划进行求解
1.使用递归进行求解
由于每个子问题形式相同，我们使用递归进行求解，直到递归到最小的子问题就返回
2.通过备忘录去重
直接递归复杂度太高，我们一般使用一个memo数组进行去重
3.写为dp数组迭代形式
返回条件就是初始值，转移方程照搬写为dp形式
二、动态规划思路
1.状态表示
有些题以-1为空，有些题以0为空，这是不同写法的缘故
因为dp迭代写法是由递归推出来的，而递归中i可以为-1，因此很多时候转换为dp后就沿用了（这些题一般不需要考虑空这种情况）
但是，有些题需要从空开始考虑，但是dp数组索引只能0开始，那么就需要手动调整+1，dp[0]就变成了空
这个一定注意，不然越看越昏
2.初始化
以一维为例，多维同理
1.求方案数
求方案数的时候，空背包装空物品表示可以装一次，因此dp[0] = 1
2.最优路径
在求单条路径上的最优值时，空背包中也能装空物品，但是由于是空物品，什么属性都没有，因此dp[0] =0
3.转移方程
1.求方案数
转移方程常常为dp[i] + dp[j]的形式（加法原理）
2.最优路径（以路径上一个参数为指标）
转移方程通常为max/min(dp[i],dp[j])的形式
3.从做选择理解转移方程
转移方程的本质就是做选择
背包问题中，我们的选择是对某一个物品，取还是不取
单子序列问题中，我们的选择是，对上一个元素（要求连续），或者前i个元素（求不连续的子序列）中进行
双序列问题中，我们的选择是，选择那条序列的指针向后移动，移动到dp[i][j]
（注意，如果是子序列问题，不能对子序列进行选择，具体理由线性dp相应章节有红字解释）
在打家劫舍问题中，我们的选择是今天是否抢劫
在股票买卖问题中，我们的选择是今天是买、卖还是不作为
4.遍历方式
1.比较在意顺序的问题
背包问题中，如果我们不在意不同路径结果的顺序（元素相同，顺序不同视为重复），那么 遍历方式先背包和先物品一样
但是，如果我们需要考虑不同路径的顺序，那么我们需要先物品后背包
具体细节参考背包问题博客
2.不太在意顺序的问题
除背包问题外，其他问题似乎都不太在意顺序问题，单序列，打家劫舍，股票问题等问题，由于是一维，不需要考虑顺序，而双序列中两条序列等价，就算是处理子序列问题，顺序也是可以颠倒的
这类问题的遍历一般参照，先进行dp[i][j]的下标遍历，然后进行选择遍历