设有向图 $G=(V,E)$, 令 $n=|V|$, $m=|E|$，$(x,y)$表示一条从 $x$ 到$y$ 的有向边，并记该条边的边权为$w(x,y)$。

存储 $G$时，我们一般使用两种存储结构：邻接矩阵和邻接表。如果$G$ 是无向图，我们可以把无向边看作两条方向相反的有向边，从而使用与有向图相同的方式存储。

从斐波那契数列说起

可能你从来没有接触过动态规划，只是隐约听别人提起过DP是种特别厉害的算法；又或许你已经看过动态规划的相关定义和教程，能够做一些像LCS、数字三角形之类的简单DP题目。

但无论你对DP了解如何，阅读本文都会使你对动态规划有更为清晰的认识。不同于你可能看过的很多资料，本文将会以一种更为崭新的视角，从更为本质而数学化的角度出发，尽力发掘出隐藏在所谓的“状态转移方程”、“最优子结构”等重重迷雾下动态规划的真实一面。