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个合法的可连乘的矩阵，以完全加括号的方式输出其最优计算顺序。