动态规划

动态规划的定义：
Add a lookup table to recussive code so that future calls to
f(...) w/some argument as computed on before can return immediately.
个人理解动态规划的核心就在于设计迭代函数。

DAG 最短路径的 dp 解法:

最长递增子序列：

此动态规划的 runtime 是 O(n² ) 不是最优解，最优解是 O(nlgn) 利用二分查找做的

编辑距离：

背包问题：

最短路径问题（有向图且无负数环）

求解单个路径：


可以认为就是 Bellman-Ford 算法。

求解所有顶点的最短路径（Floyd-Warshall）：
比 Bellman-Fold 求每个点要快。

矩阵链式相乘

旅行商问题