目录
动态规划法的基本思想
多段图的基本想法
代码块（Java）
运行结果
动态规划法的基本思想:
- 将大问题划分成若干个小问题进行解决，从而一步步获取最优解
- 动归从上到下分析问题，从下到上解决问题
- 动归与分治法相似，其基本思路都是将待求问题分解成若干个子问题，先求解子问题，再从子问题中找到原问题的解
- 动归与分治法不同之处：动归的子问题不是相互独立的，他们之间往往存在依赖关系，而分治法的子问题都是相互独立的
多段图的基本想法：
从源点出发，找出一条到达终点时权值最小的路径
| 下标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 元素值 | 4 | 2 | 3 | 8 | 7 | 10 | 13 | 13 | 16 |
| 状态转移 | 0->1 | 0->2 | 0->3 | 2->4 | 3->5 | 2->6 | 4->7 | 5->8 | 8->9 |
代码块（Java）：
const int MAX=1000; //假定边上的权值最大不超过1000
#define N 10
int arc[10][10]
int CreatGraph()
{//创建图
int i,j,k;
int weight; //权值
int vnum,arcnum; //vnum为顶点个数，arcnum为边数
cout<<"请输入顶点的个数和边数：";
cin>>vnum>>arcnum;
for(i=0;i<vnum;i++) //初始化图的代价矩阵，将每一个都设为无穷
for(j=0;j<vnum;j++)arc[i][j]=MAX;
for(k=0;k<arcnum;k++) //建立图的代价矩阵，将两点之间有边的填入他们所对应的权值
{
cout<<"请输入两个顶点和他们所对应的权值";
cin>>i>>j>>weight;
arc[i][j]=weight; //有边，填入权值
}
cout<<"已初始化完多段图！";
return vnum; //返回顶点个数
}
int BackPath(int n) {int i,j,temp;int cost[N],path[N]; //cost数组存储路径长度，path存储路径for(i=1;i<n;i++) { //初始化第1个到第n个顶点的路径长度cost为无穷，路径path为-1cost[i]=MAX; path[i]=-1; }cost[0]=0;path[0]=-1; // path[0]=-1表示顶点0为起点for(j=1;j<n;j++) { //填表for(i=j-1;i>=0;i--) { //i是j的前驱，考察所有入边if(arc[i][j]+cost[i]<cost[j]) { //找出到达j的最短路径长度和前驱cost[j]=arc[i][j]+cost[i]; //记录最短的路径长度path[j]=i; //记录前驱的下标}}}
//输出最短路径cout<<n-1; //输出终点i=n-1;while(path[i]>=0) { //依次输出path[i]，path[i]<0说明已到达多段图的起点cout<<"<-"<<path[i]);i=path[i]; //找到路径上顶点i的前一个顶点}return cost[n-1]; //返回最短路径长度
}
运行结果：
