定义一组子问题，按照由小到大，以小问题的解答支持大问题求解的模式，依次解决所有的子问题，并最终得到原问题的解答。
隐含思想
DAG有向无圈图的拓扑排序
节点对应于我们定义的子问题，边表示子问题间的依赖关系：即如果求解子问题B必须依赖子问题A的解答，则（概念上）存在一条由A到B的边。
子问题性质
存在子问题间的一种排序以及如下的关联关系：对于任意一个 子问题，这种关联关系说明了如何在给定（在排序中）相对其“较小”的子问题的解的前提下，求得该子问题的解
妙处
恰当地选择子问题，使得所有重要的信息都得以保存并便于今后使用
常见子问题模式
模式1
输入为x1, x2, ..., xn，子问题为x1, x2, ..., xi。
最终子问题数量将为线性。
模式2
输入为x1, x2, ..., xn和y1, y2, ..., ym，子问题为x1, x2, ..., xi和y1, y2, ..., yj。
最终子问题数量为O(m*n)
模式3
输入为x1, x2, ..., xn，子问题为xi, x(i+1), ..., xj。
最终子问题数量为O(n^2)。
模式4
输入为树，子问题为其子树。
若树有n个节点，则最终子问题数量为O(nlogn)。
最长递增子序列
输入：一个数字序列a1、a2、...、an。
输出：从以上序列中按顺序选出的一个子集，并且严格单调递增，形如a(i1)、a(i2)、a(ik)，其中1<=i1<i2<...<ik<=n。
策略1
为每个元素建立一个对应的节点，对任意两个存在递进关系的元素ai和ak（即同时满足i<j且ai<ak），增加一条连接两者对应节点的有向边(i, j)
形成dag，求递增子序列问题变为寻找dag中的最长路径
for j = 1,2,...,n:
L(j) = 1 + max{L(i):(i, j) in E}
return max{L(j)}
L(j)是以序列中j为终点的最长路径，即对应于最长递增子序列的长度
实现
- 为方便图的邻接表表示，可变形为
for i = 1,2,...,n:
for (i, j) in E:
L(j) = max {L(j), L(i) + 1}
return max{L(j)}
see implement: dp.LongestIncreSub
- 求反转图G的邻接表表示
此时无需构造原图G
时间复杂度max{O(n^2), O(V+E)}
策略2
子问题：将LCS(i)记做包含的最长递增子序列长度。
LIS[i] = max{1,LIS[k]+1}，其中，对于任意的k<=i-1，arr[i] > arr[k]。
最长公共子序列LCS
输入：两个序列X)，Y)。
输出：一个序列S任意删除若干个字符得到新序列T，则T叫做S的子序列。两个序列X和Y的公共子序列中，长度最长的那个，定义为X和Y的最长公共子序列。
策略
子问题：将LCS(i, j)记做)与)的最长公共子序列长度。
考察
即
=\begin{cases}0 & if ; i=0 ; or ; j=0\LCS(i-1, j-1)+1 & if ; i>0, j>0, and ; x_i = x_j\max {LCS(i-1, j), LCS(i, j-1)} & if ; i>0, j>0, and x_i != x_j\end{cases})
时间复杂度max{O(n^2)}
变体1：最长公共子串
子序列不要求子序列中的字符在原序列中连续，而子串要求连续。
策略
子问题：)表示以
考察
即
=\begin{cases}0 & if;i=0;or;j=0\L(i-1, j-1)+1 & if;i>0, j>0, and ; x_i = x_j\0 & if ; i>0, j>0, and x_i != x_j\end{cases})
在上述过程中记录)的最大值，最后即可得到最长公共子串的长度
时间复杂度O(n^2)
最长公共子串类似：最大子串和
PAT1007. Maximum Subsequence Sum
输入：给定一个序列X)。
输出：找出该序列具有最大和的子串。如果该序列所有数均为负数，则输出0。
策略
子问题：
考察
即
=\begin{cases}x_i & if ; i=0 ; or ; Sum(i-1)<=0\x_i + Sum(i-1) & if ; Sum(i-1)>0\end{cases})
的最大值，并根据第一种情况重新修改tempLeft（当前子串左边开始位置）。最后即可得到最大子串和以及最大子串。
时间复杂度O(n)
空间复杂度O(1)
算法过程中只需存储上一步的Sum和位置信息
变体2：最长递增子序列LIS
- 对输入序列X进行排序，得到序列Y
- 求解序列X和Y的最长公共子序列，即是序列X的最长递增子序列
时间复杂度O(n^2)
编辑距离
随意插入空隙“-”到每个字符串中使两个字符串对齐，对于该种对齐方式，代价为两个字符串对应字母不相同的列数。如：
S - N O W Y
S U N N - Y
SNOWY和SUNNY该种对齐方式的代价为3
编辑距离是指两个字符串的各种对齐所可能具有的最小代价。
策略
子问题：定义E(i, j)为寻找两个字符串x[1...i]与y[1...j]之间的编辑距离。
由于要将E(i, j)表示为较之更小的子问题的表达式，我们考虑x[1...i]与y[1...j]所有对齐中最右侧的列的可能情况:
- x[i]与-
- -与y[j]
- x[i]与y[j]
因此，E(i, j) = min{1+E(i-1, j), 1+E(i, j-1), diff(x[i], y[j])+E(i-1, j-1)}
当x[i]=y[j]时，diff()取0；否则取1
所有子问题E(i, j)的解构成一个二维表，要保证求解顺序（E(i-1, j), E(i, j-1)和E(i-1, j-1)总是在E(i, j)之前求解）
算法如下：
for i = 0, 1, 2 ... m:
E(i, 0) = i
for j = 1, 2 ... n:
E(0, j) = j
for i = 1, 2 ... m:
for j = 1, 2 ... n:
E(i, j) = min{E(i-1, j)+1, E(i, j-1)+1, E(i-1, j-1)+diff(i,j)}
return E(m, n)
see implement: dp.EditingDistance
时间复杂度为O(m*n)
扩展
在二维表中，令{(i-1, j-1)->(i, j) : x[i]=y[j]}中边的长度置为0，并将其他所有边的长度置为1。则求编辑距离问题变为求dag中的最短路径，即点{0,0}与{m,n}之间的最短路径。
在该路径上，向下的移动表示删除，向右为插入，而对角线移动表示匹配或者替换。
背包问题
一共有n件物品，分别重w1,w2, ..., wn，价值v1,v2,...,vn。背包最多能装W磅，如何组合才能使背包携带的价值最高。
广泛应用于需要机遇有限资源进行选择判断的领域
多副本的背包问题
每种物品的数量无限
1. 子问题：考虑容量较小的背包
定义K(w) = 容量w可以容纳的最高价值
若K(w)的最优解包含物品i，将物品i去掉，则会留下K(w-wi)的最优解。不知道包含哪些i，因此尝试所有的可能
 = max_{i:w_i<=w} {K(w-w_i)+v_i})
K(0) = 0
for w = 1 to W:
K(w)= max{K(w-w(i))+v(i):wi<=w}
return K(W)
时间复杂度O(nW)
see implement: dp.bag.MultiBagProWithCapa
构造DAG
针对每个w构造节点，其中w in 0~W。对于每个节点与每个物品，使用该物品的容量确定边的终点，使用该物品的价值确定边的权值，可以构造出一个DAG。求背包所能容纳的最高价值最终归结为寻找该DAG的最长路径。
2. 子问题：考虑较少的物品种类
TODO
单副本的背包问题
每种物品都只有一件
策略
在K(w)子问题中包含关于哪件物品已经被使用过的信息。
定义子问题K(w, j) = 基于背包容量w和物品1, ..., j所能得到的最高价值
用更小的子问题表示K(w, j)：
 = max(K(w-w_j,j-1)+v_j, K(w, j-1)))
initialize all K(0, j) = 0 and all K(w, 0) = 0
for j = 1 to n:
for w = 1 to W:
if w(j) > w: K(w, j) = K(w, j-1)
else: K(w, j) = max{K(w, j-1), K(w-w(j), j-1)+v(j)}
时间复杂度O(nW)
see implement: dp.bag.SingleBagPro
矩阵链式相乘
一个mn的矩阵与一个np的矩阵相乘，约需要进行mnp次乘法。通过在矩阵链式相乘公式的不同位置插入括弧，我们可以得到很多不同的计算方式，那么哪种乘法次序代价最小？
自然的表示
满二叉树：每个矩阵对应一个叶节点，树根为最终的乘积，而树的内部节点表示中间过程的部分乘积。各种可能的乘法次序对应不同的满二叉树。
如果一个树最优，那么其子树必然也最优
策略
假设我们需要计算
定义 = the ; minimum ; cost ; of ; computing A_iA_{i+1}...A_j)
C(i, j)可分割为C(i, k)和C(k+1, j)两个子问题，即
 = min_{i<=k<j}[C(i,k) + C(k+1, j) + m_{i-1}m_km_j])
由于C(i, k)的维数为，C(k+1, j)的维数为
求解顺序：当求解到某个子问题时，比该子问题规模小的子问题已被求解。
因为(i,j)坐标并不在(i+1, j)坐标的下边或右边，此时无法按照从上至下，从左至右的求解顺序
for i = 1 to n: C(i, i) = 0
for s = 1 to n-1:
for i = 1 to n-s:
j = i+s
C(i, j) = min{C(i,k) + C(k+1, j) + m(i-1)*m(k)*m(j):i<=k<j}
return C(1, n)
see implement: dp.MatrixChain
时间复杂度O(n^3)
动态规划 VS 递归记忆
记忆：递归算法记住之前的调用结果
- 优点：记忆只会求解那些实际被用到的子问题
- 缺点：递归所具有的的间接开销通常较高，其大O符号所包含的常数因子相对而言较大
写在最后
- 立个Flag，
TODOwill be done some day。 - 渣代码，且轻喷:worried:。
