第七章 动态规划
一、递归求解：
递归问题的关键是解决初始值和递推公式，从而将复杂问题分解为简单问题直至初始值对应的极简问题，从而得到答案。
套路：初始值+递归公式。
Trick：将求出的值存储在数组中以便复用。
二、问题1：最长递增子序列（LIS：Longest increasing subsequence）：
递增子序列定义：从已知序列{a1,a2,a3…an}中取出若干数为原序列的子序列{ai1,ai2…aim}，当下标ix>iy时，aix>aiy，则该序列是原序列的一个递增子序列。
第一个元素的LIS即为1，之后从序列中读入第j位新元素，之前的各位对应的LIS已知，所以如果之前第i位元素小于新元素时，则可以与j-1位元素的LIS长度Lmax比较，进行更新。
递推公式：
dp[1] = 1;
dp[j] = max{Lmax, dp[i] + 1| i<j && ai<aj}
三、问题2：最长公共子序列（LCS：longest common subsequence）：
最长公共子序列定义：在字符串S中按照先后顺序依次取出若干字符构成原字符串的子串。两个字符串S1和S2，求一个最长公共子串，即为最长公共子序列。
四、总结：状态与状态转移方程：
套路：
- 寻找一个状态，该状态描述问题的当前状况，状态间的转移完全依赖于各状态本身。
- 数字量之间的递推关系即为状态转移的规则，也称为状态转移方程。确定了状态的转移规则即确定了怎么样由前序状态递推求出后续状态。
五、背包问题：
该问题主体讲解见《王道机试指南》背包篇
问题一：为何0-1背包的状态转移方程是dp[i][j] = max{dp[i-1][j-w]+v, dp[i-1][j]}? 为什么比较的右项是dp[i-1][j]而不是dp[i-1][j-w]？
因为你在这里要更新的是dp[i][j] ，并不能仅仅只考虑dp[i-1][j-w]， 如果是这样的话dp[i-1][j-w]+v肯定比dp[i-1][j-w]大，还要比什么。这样写的目的是将加入第i个物品后的总价值与不加入该物品但是达到同样达到相同体积的背包总价值相比较，如果价值更大则加入第i件物品。
比如之前已经循环过体积10,30的物品，达到40时的价值为4，现在考虑体积40，价值为3的物品，相同体积加入它的价值就不如前者高，所以不放入背包。
问题二：为什么0-1背包中j要逆序循环？
因为每个物品只能使用一次。比如我们有五个物品，体积为10, 30, 20, 40，价值为1，2，3, 4。考虑正序循环代入优化后的0-1背包方程，放入第一个物品时有dp[10]=1, 由于我只有一个物品，因此在计算dp[20]的时候我希望dp[10]还是初始状态，但是在这种情况下dp[20]就会受到dp[10]的影响变为2。
逆序循环就不会存在这个问题，因为j-w<j，所以每次逆序循环的时候都可以保证dp[j-w]未受到之前循环的影响。
问题三：完全背包如何解决每种物品数都无限的问题？
正好利用了问题二，我现在每件物品都不限制数量，那么正序循环正好可以考虑到物品叠加利用的效果。
问题四：多重背包怎么拆分的？
比如一种物品数量为10，拆分成1,2,4,8,3,这五个数确实可以组合成1-10的任意整数。