1．多段图中的最短路径问题
【问题描述】
建立一个从源点S到终点T的多段图，设计一个动态规划算法求出从S到T的最短路径值，并输出相应的最短路径。

#include<iostream>
#include<cmath>
#include<string.h>
#include<stdio.h>
using namespace std;
int  dp[1222222],alone[1222222],a[1222222];
int main()
{
   int i,j,n,m;
   while(~scanf("%d",&m))
   {
       scanf("%d",&n);
       memset(dp,0,sizeof(dp));
       memset(alone ,0,sizeof(alone));
       for(i=1;i<=n;i++)scanf("%d",&a[i]);
       int tmax;
       for(i=1;i<=m;i++)//分i段
       {
           tmax=-(1<<30);

           for(j=i;j<=n;j++)
           {
               dp[j]=max(dp[j-1],alone[j-1])+a[j];


               printf("%2d %2d %2d\\n",a[j],alone[j-1],dp[j]);
               if(j>i)alone[j-1]=tmax;

               if(tmax<dp[j])tmax=dp[j];

           }

       }
       printf("%d\\n",tmax);
   }
   return 0;
} ``` 





2．有向无环图中的最短路径问题
【问题描述】
建立一个从源点S到终点E的有向无环图，设计一个动态规划算法求出从S到E的最短路径值，并输出相应的最短路径。

include <iostream>

include <limits.h>

using namespace std;

void Init_Graph(int N,int **S)
{
int i,j;
cout<<"输入边的长度：输入1 2 4 表示点1 与 2的边的长度为 4：首数字为0表示结束输入"<<endl;
cin>>i;
while(i!=0)
{
cin>>j;
cin>>S[i][j];
cin>>i;
}
}

void DP(int N,int **S,int *dist,int *from)
{
int i,j;
for(j=0;j<N+1;j++)
{
if(S[1][j]<INT_MAX)
{
dist[j]=S[1][j];
from[j]=1;
}
}

for(j=2;j<N+1;j++)
{
    for(i=2;i<j;i++)
    {
        if(S[i][j]<INT_MAX)
        {
            if(dist[i]+S[i][j]<dist[j])
            {
                dist[j]=dist[i]+S[i][j];
                from[j]=i;
            }
        }
    }
}
cout<<"最短路径为：";
i=6;
cout<<N<<"  "<<from[i]<<"  ";
i=from[i];
while(i!=1)
{
    cout<<from[i]<<"  ";
    i=from[i];
}
cout<<"\\n";
cout<<"最短距离为："<<dist[N]<<endl;

}

int main()
{
int N;
int S,dist,from;
int i,j;
cout<<"输入点的个数：";
cin>>N;

S=new int*[N+1];
for(i=0;i<N+1;i++)
{
    S[i]=new int[N+1];
    for(j=0;j<N+1;j++)
    {
        S[i][j]=INT_MAX;
    }
}
dist=new int[N+1];
for(i=0;i<N+1;i++)
{
    dist[i]=INT_MAX;
}
from=new int[N+1];
for(i=0;i<N+1;i++)
{
    from[i]=0;
}

Init_Graph(N,S);
DP(N,S,dist,from);

for(i=0;i<N+1;i++)
{
    delete []S[i];
}
delete []S;
delete []dist;
delete []from;
return 0;

}

3．最长递增子序列问题
【问题描述】
给定一个整数数组，设计一个动态规划算法求出该数组中的最长递增子序列。


4．矩阵连乘问题
【问题描述】
给定n个矩阵{A1，A2，…,An},其中AiAi+1是可乘的，i=1，2，…，n-1,考察这n个矩阵的连乘积A1A2…An，设计一个动态规划算法，求出这个矩阵连乘积问题的最优计算顺序。
实现要求：随机生成n个合法的可连乘的矩阵，以完全加括号的方式输出其最优计算顺序。