提示：本文章不含代码，纯应试解题~（中国地质大学（武汉）研究生算法考试题目）
文章目录
前言
动态规划（Dynamic Programming，简称DP）是一种算法策略，用于解决具有重叠子问题和最优子结构特性的问题。多段图问题是一种特殊的动态规划问题，通常涉及到将一个整体问题分解成多个子问题，这些子问题可以看作是图中的多个段落或部分，然后通过解决这些子问题来解决整个问题。
说人话就是——想象一下，你正在规划一次旅行，你的目标是从一个城市（起点）出发，经过几个不同的城市（中间点），最终到达另一个城市（终点）。每个城市之间都有道路连接，每条道路都有其长度（费用）。你的目标是找到一条最短的路线，让你能够从起点城市到达终点城市，
一、问题描述
1.题目
如下图所示，多段图G是一个带权的有向图：
可以看到总共有5个阶段（在图中以
V
1
V_1
V1~
V
5
V_5
V5表示），起点的标号为1，终点的标号为12。
注意：多段图问题有且只有一个起点和终点。
2.符号描述
c o s t ( i , j ) cost(i,j) cost(i,j)代表第 i i i阶段的第 j j j状态距离起点的最短路径。举个栗子—— c o s t ( 2 , 2 ) cost(2,2) cost(2,2)表示的就是第2阶段（也就是图中所表示的 V 2 V_2 V2段）里编号为2的点到起点1最短的距离，很容易知道起点1到编号为2的点的距离是9，所以 c o s t ( 2 , 2 ) = 9 cost(2,2)=9 cost(2,2)=9
3.公式介绍
c o s t ( i , j ) = m i n { c o s t ( i − 1 , l ) + c ( l , j ) } cost(i,j)=min\{cost(i-1,l)+c(l,j)\} cost(i,j)=min{cost(i−1,l)+c(l,j)}
c o s t ( i , j ) cost(i,j) cost(i,j)是一个动态规划的状态，表示到达第i个阶段，第j个编号的最短路径
c o s t ( i − 1 , j ) cost(i-1,j) cost(i−1,j)是第i-1个阶段，编号为l的成本，这里的l是一个中间变量
c ( l , j ) c(l,j) c(l,j)是编号为l的点到编号为j的距离，这个距离是固定的，在图中以边上权重表示，例如 c ( 1 , 2 ) = 9 c(1,2)=9 c(1,2)=9
温馨提示：一定要区分 c o s t cost cost和 c c c所表示的是不一样的哦~如果对公式不太清楚可以看看后面的解题步骤，就会很容易懂啦！（公式只是形式化表达，主要是看图）
二、解题步骤
1. s t e p 1 step \quad 1 step1
c
o
s
t
(
1
,
1
)
=
0
cost(1,1)=0
cost(1,1)=0
这里表示的第一阶段的点到编号为1的点的距离，当然就是0啦，一般第一步就是算起点到起点之间的距离
2. s t e p 2 step \quad 2 step2
首先，我们要对第二个阶段每一个点进行计算，这里阶段2有编号为2,3,4,5的点，即要计算 c o s t ( 2 , 2 ) cost(2,2) cost(2,2)、 c o s t ( 2 , 3 ) cost(2,3) cost(2,3)、 c o s t ( 2 , 4 ) cost(2,4) cost(2,4)、 c o s t ( 2 , 5 ) cost(2,5) cost(2,5)
温馨提示：这里 c o s cos cos里的前面那个数表示的是阶段数哦~
c o s t ( 2 , 2 ) = m i n { c o s t ( 1 , 1 ) + c ( 1 , 2 ) } = 9 cost(2,2)=min\{cost(1,1)+c(1,2)\}=9 cost(2,2)=min{cost(1,1)+c(1,2)}=9
c o s t ( 2 , 2 ) cost(2,2) cost(2,2)表示第2个阶段编号为2的点距离起点1得最短距离，后面就不进行解释啦~
c o s t ( 2 , 3 ) = 7 cost(2,3)=7 cost(2,3)=7
c o s t ( 2 , 4 ) = 3 cost(2,4)=3 cost(2,4)=3
c o s t ( 2 , 5 ) = 2 cost(2,5)=2 cost(2,5)=2
3. s t e p 3 step \quad 3 step3
接下来就是对第3个阶段的每一个编号的点进行求解啦，即要计算 c o s t ( 3 , 6 ) cost(3,6) cost(3,6)、 c o s t ( 3 , 7 ) cost(3,7) cost(3,7)、 c o s t ( 3 , 8 ) cost(3,8) cost(3,8)。
这里与 s t e p 2 step2 step2有一点不同的是，要体现 m i n min min的作用了，因为这里这一个阶段的每一个编号的点可能有多个箭头指向它，而 s t e p 2 step2 step2中每一个编号的点只有起点1指它。
c o s t ( 3 , 6 ) = m i n { c o s t ( 2 , 2 ) + c ( 2 , 6 ) c o s t ( 2 , 3 ) + c ( 3 , 6 ) } = 9 cost(3,6)=min\left\{ \begin{aligned} cost(2,2)+c(2,6) \\ cost(2,3)+c(3,6) \\ \end{aligned} \right \}=9 cost(3,6)=min{cost(2,2)+c(2,6)cost(2,3)+c(3,6)}=9
温馨提示：个人觉得可以不用套那个公式，直接看图就行啦。你看阶段3的编号为6的点，是不是只有阶段2中编号为2和3的点指向它，所以只要比较两个就行了。而在 s t e p 2 step2 step2中我们已经计算出了 c o s t ( 2 , 2 ) cost(2,2) cost(2,2)、 c o s t ( 2 , 3 ) cost(2,3) cost(2,3)了，然后在分别加上编号为2到编号为6的距离 c ( 2 , 6 ) = 4 c(2,6)=4 c(2,6)=4，以及编号为3到编号为6的距离 c ( 3 , 6 ) = 2 c(3,6)=2 c(3,6)=2就行啦~后面就不对此进行解释啦！
c o s t ( 3 , 7 ) = m i n { c o s t ( 2 , 2 ) + c ( 2 , 7 ) c o s t ( 2 , 3 ) + c ( 3 , 7 ) c o s t ( 2 , 5 ) + c ( 5 , 7 ) } = 11 cost(3,7)=min\left\{ \begin{aligned} cost(2,2)+c(2,7) \\ cost(2,3)+c(3,7) \\ cost(2,5)+c(5,7) \end{aligned} \right \}=11 cost(3,7)=min⎩ ⎨ ⎧cost(2,2)+c(2,7)cost(2,3)+c(3,7)cost(2,5)+c(5,7)⎭ ⎬ ⎫=11
c o s t ( 3 , 8 ) = m i n { c o s t ( 2 , 2 ) + c ( 2 , 8 ) c o s t ( 2 , 4 ) + c ( 4 , 8 ) c o s t ( 2 , 5 ) + c ( 5 , 8 ) } = 10 cost(3,8)=min\left\{ \begin{aligned} cost(2,2)+c(2,8) \\ cost(2,4)+c(4,8) \\ cost(2,5)+c(5,8) \end{aligned} \right \}=10 cost(3,8)=min⎩ ⎨ ⎧cost(2,2)+c(2,8)cost(2,4)+c(4,8)cost(2,5)+c(5,8)⎭ ⎬ ⎫=10
太好了，阶段三结束啦（小声哔哔：数学公式好难敲）
4. s t e p 4 step \quad 4 step4
然后，就是对第4个阶段的每一个编号的点进行求解啦，即要计算 c o s t ( 4 , 9 ) cost(4,9) cost(4,9)、 c o s t ( 4 , 10 ) cost(4,10) cost(4,10)、 c o s t ( 4 , 11 ) cost(4,11) cost(4,11)。
c o s t ( 4 , 9 ) = m i n { c o s t ( 3 , 6 ) + c ( 6 , 9 ) c o s t ( 3 , 7 ) + c ( 7 , 9 ) } = 15 cost(4,9)=min\left\{ \begin{aligned} cost(3,6)+c(6,9) \\ cost(3,7)+c(7,9) \\ \end{aligned} \right \}=15 cost(4,9)=min{cost(3,6)+c(6,9)cost(3,7)+c(7,9)}=15
c o s t ( 4 , 10 ) = m i n { c o s t ( 3 , 6 ) + c ( 6 , 10 ) c o s t ( 3 , 7 ) + c ( 7 , 10 ) c o s t ( 3 , 8 ) + c ( 8 , 10 ) } = 14 cost(4,10)=min\left\{ \begin{aligned} cost(3,6)+c(6,10) \\ cost(3,7)+c(7,10) \\ cost(3,8)+c(8,10) \end{aligned} \right \}=14 cost(4,10)=min⎩ ⎨ ⎧cost(3,6)+c(6,10)cost(3,7)+c(7,10)cost(3,8)+c(8,10)⎭ ⎬ ⎫=14
c o s t ( 4 , 11 ) = m i n { c o s t ( 3 , 8 ) + c ( 8 , 11 ) } = 16 cost(4,11)=min\left\{ \begin{aligned} cost(3,8)+c(8,11) \\ \end{aligned} \right \}=16 cost(4,11)=min{cost(3,8)+c(8,11)}=16
温馨提示：由于编号11只有一个点指向它，所以也可以不用写 m i n min min也行哈~
5. s t e p 5 step \quad 5 step5
Oh~yeah，终于到最后一个阶段啦！这个阶段就是对终点12进行求解啦即要计算 c o s t ( 5 , 12 ) cost(5,12) cost(5,12)。
c o s t ( 5 , 12 ) = m i n { c o s t ( 4 , 9 ) + c ( 9 , 12 ) c o s t ( 4 , 10 ) + c ( 10 , 12 ) c o s t ( 4 , 11 ) + c ( 11 , 12 ) } = 16 cost(5,12)=min\left\{ \begin{aligned} cost(4,9)+c(9,12) \\ cost(4,10)+c(10,12) \\ cost(4,11)+c(11,12) \\ \end{aligned} \right \}=16 cost(5,12)=min⎩ ⎨ ⎧cost(4,9)+c(9,12)cost(4,10)+c(10,12)cost(4,11)+c(11,12)⎭ ⎬ ⎫=16
完结啦， c o s t ( 5 , 12 ) = 16 cost(5,12)=16 cost(5,12)=16。这个结果就是我们要求的。它表示的就是第5个阶段编号为12的点（即终点）距离起点1得最短距离。
总结
个人觉得，动态规划问题的每一个阶段的结果都需要通过上一个阶段的结果得出，一层包裹着一层的感觉呀~
本人能力有限，如果有错误，请批评指正，本人感激不尽！