动态规划就要从 DAG 聊起：
我们之前 （有向图中的 DFS）中提到过 DAG 的线性化，DP 的问题实际上就是在这样一个有拓扑排序的 DAG 上进行的，比如计算距离：
LIS
最经典的一个问题！我们需要求最长上升子序列
通过大小关系建有向边实际上就把问题变成了 DAG 上的最长路径。于是有简单的算法
以这个为例子，DP 的本质是子问题的解决之间的转移
似乎只是为了介绍 DP 的想法，故没有讲更 technical 的内容了（如
的算法）
编辑差距 Edit Distance
这里的情境可以考虑一个电子词典机（我年纪小的时候还是有这个东西的）或者拼写检查器，或者单纯的输入法联想也可以。对于模糊单词和联想单词的距离的测度问题，我们想到的比较理想的距离为编辑距离，即最好条件下修改前者的字母变为后者的修改次数
比如
抽象为下面两个集合之间的距离
转移公式的来源是寻找子问题，而不重不漏（不过这里只需要多种情况取最优，不漏就行啦）的一种好办法是分类讨论。我们可以考虑最后一步是改 / 删 A / 删 B，于是得到转移公式
Knapsack 背包问题
这个问题（包括下面的矩阵链）由于讲过，就略写了
无限背包问题（可重复）
直接对最后一个分类讨论，容易知道是
0-1 背包
需要分二维变为 
也是
矩阵链乘法
希望找到最优的相乘顺序，使用中间的相乘间隔分类讨论，作区间 DP 即可
TSP 旅行商问题
TSP 问题，即对
注：关于 TSP 问题，一般的 TSP 问题目前是不可近似的！（除非 P = NP），不过如果边权满足三角不等式（e.g. 边权就是欧几里得长度），则已经有算法可以得到略小于
的近似比，欧几里得长度下则有更好的结果，请见 Travelling salesman problem - Wikipedia 以进一步了解
暴力显然是 
每个这样的子问题需要
综上，得到了一个
树中独立集
一般图中的最大独立集是 
只需要分取不取 root 就可以了，每个顶点只会用到常数次（parent 和 grandparent 都是固定的），所以一共就是