1.何为动态规划？
书接上文，可以把分治法看作是：把一个问题分成若干个独立的子问题。如果子问题不独立呢？
拿$Fibonacci$数列问题来说，每一个子问题都和其他子问题有关系。这个时候用分治法就不是很合理了，比如说，求解$Fib(5)$就必然要求$Fib(4),Fib(3)$，而求$Fib(4)$还要求一次$Fib(3)$，这就导致，有的子问题要被多次求解，专业点的说法就是子问题重叠。
这时候George说了，“那我们不妨从小问题开始求，把结果都记下来，最后一步步求解到原问题吧”。
这就是动态规划：把原始问题划分成若干个子问题，求解每个子问题仅一次，并将其结果保存，以后用到时直接存取，不重复计算，节省计算时间。
什么样的问题适用于动态规划呢？
优化问题：问题可能有很多解，每个可能的解都对应有一个值，这个值通常称为代价。优化问题是要在该问题所有可能的解中找到代价最大/最小的解，即问题的一个优化解（最优解）。
重叠问题:在问题的求解过程中，很多子问题的解将被多次使用。
动态规划求解的步骤大致为：简化原问题-建立递归方程-求解子问题-求解原问题。
2.矩阵乘法链
输入：表达式：$A_1\times A_2\times \cdots\times A_n$，其中$A_i$是$p_{i-1}\times p_i$矩阵。
输出：乘法的最小代价方法，代价为乘法运算次数。
最小代价？代价从哪里来？根据矩阵的乘法原理，$A_{10\times 100}\times B_{100\times 5}\times C_{5\times 50}=(A\times B)\times C=A\times (B\times C)$。对于$(A\times B)\times C$来说，$A\times B$的代价是$10\times 100\times 5=5000$，而产出一个$10\times 5$矩阵，与$C$相乘，代价为$10\times 5\times 50=2500$，相加得$7500$。同理，$A\times(B\times C)$代价为$75000$。
引入概念：
最优子结构：问题最优解由子问题最优解组成。
讨论下图中所有的乘法方案最优性：
设$C[i,j]$为计算$A_i\times A_{i+1}\times\cdots\times A_j$的最小代价，可以作出代价的递归方程：
$$
C[i,j]=min_{i\leq k< j}{C[i,k]+C[k+1,j]+(i-1)kj},i<j\
C[i,j]=0,i=j
$$
递归得到两个括号内的最优乘法方案，合并就是最优乘法方案了。但是：
不难看出有子问题重叠。
那么根据动态规划的思想，计算$C[i,j]$需要计算出每一个$C[a,b],i\leq a\leq j,a\leq b\leq j$，可作出下图：
每个红线上的矩阵链长度相同。从最长的对角线一直求到目标长度。
时间复杂度为$O(n^3)$，空间复杂度为$O(n^2)$。
3.最长公共子序列
输入：$X=(x_1,x_2,x_3,\cdots,x_m),Y=(y_1,y_2,y_3,\cdots,y_n)$
输出：$Z=(z_1,z_2,z_3,\cdots)$为$X,Y$最长的公共子序列。
由此推得，子问题有重叠性：
对于$X,Y$的所有子串，可以列出公共子序列长度方程：
$$
C[i,j] = 0\ \ \ \ ij=0\
C[i,j]=C[i-1,j-1]+1\ \ \ \ i,j>0,x_i=y_j\
C[i,j]=Max(C[i,j-1],C[i-1,j])\ \ \ \ i,j>0,x_i\neq y_j
$$
对于每一个$x_i,y_j$，都依靠上式计算，自底向上求解，即在求$C[i,j]$之前，先求出$C[i-1,j-1],C[i-1,j],C[i,j-1]$，并记录下此时对应的子问题，作出下表：
每一个格子，里面的箭头表示其对应的子问题，比如如果对某个格子来说，$x_i=y_j$，箭头就指向$C[i-1,j-1]$；里面的数字代表公共子序列的长度。
时间复杂度为$O(mn)$，因为要讨论$mn$个元素，而每个元素讨论的时候复杂度是$O(1)$；构造子序列，即查看子序列的具体内容，复杂度是$O(m+n)$，因为可以看作从右下角走到边界。合并起来时间复杂度是$O(mn)$
空间复杂度是$O(mn)$。
4.0-1背包问题
问题概述：给定$n$种物品和一个背包，物品$i$的重量是$w_i$，价值$v_i$, 背包承重为$C$, 问如何选择装入背包的物品，使装入背包中的物品的总价值最大？对于每种物品只能选择完全装入或不装入，一个物品至多装入一次。
抽象成一个问题：
输入：给定$C>0,w_i>0,v_i>0,1\leq i \leq n$
输出：$(x_1,x_2,\cdots,x_n),x_i\in {0,1},Q=\sum_{1\leq i\leq n}w_ix_i\leq C$，求满足条件的最大$Q$。
原问题，记作：$(x_1,x_2,x_3,\cdots,x_n),C$，意思是把$(x_1,x_2,x_3,\cdots,x_n)$装入容量为$C$的背包中，根据是否装第一个物品，可划归成两个子问题：
- $(x_2,x_3,\cdots,x_n),C-w_1$
- $(x_2,x_3,\cdots,x_n),C$
那么，可以分析出子问题重叠：
作递归方程，设$C[i,j]$是可选物品为$i,i+1,\cdots,n$，背包容量为$j$时的最大价值：
$$
C[i,j]=C[i+1,j],0\leq j \leq w_i\
C[i,j]=Max(C[i+1,j],C[i+1,j-w_i]+v_i),j>w_i
$$
第一个式子的意思是，装不下，只好讨论下一个物品。第二个式子则是讨论装与不装哪个更划算一些。
根据上面的这个表达式，参考最长公共子序列的计算方式，可以求解。
时间复杂度是$O(Cn)$，空间复杂度是$O(Cn)$。