动态规划：即将要求解的问题分解成多个相互重叠的子问题，根据子问题找到递推关系，即动态规划函数，然后将各子问题的解填入表中，下次就可以直接查表得到子问题的解啦。

动态规划求最短路径问题：

求解从顶点0到顶点9的最短路径，如图：

从顶点0到顶点9的最短路径可以分解为从从起点到顶点9的前一个顶点的最短距离+该顶点到9的距离。这样，从起点到每个顶点的距离都可以分解为起点到该顶点的前一个点的最短距离+前一个点到该点的距离。

用 d(i) 表示到顶点i的最短路径，c(i,j) 表示从顶点 i 到 j 的路径。

注：这里 i-1 表示顶点 i 的前一个顶点，不一定有 (i-1)+1=i，例如该图中顶点9的前一个顶点有两个：7和8，取7还是8，取决于起点到7和8的距离谁更短。这样每一个顶点都可以分解为这样的子问题。