问题描述：
随机产生一个n行m列的整数矩阵，如图所示即随机产生的一个7行5列的数值矩阵，在整数矩阵中寻找从左上角至右下角，每步可向下（D）或向右（R）或斜向右下（O）的一条数值和最小的路径。
27 28 29 18 26
16 13 19 14 27
32 22 39 26 21
10 30 23 20 18
13 11 30 29 20
10 13 21 17 36
34 37 15 22 36
设计要点：
应用动态规划设计，即从右下角逐行反推左上角。确定n、m后，随机产生的整数二维数组a(n,m)作矩阵输出，同时赋给部分和数组b(n, m)。
这里数组b(i,j)为点(i,j)到右下角的最小数值和，stm(i,j)是点(i,j)向右（R）或向下（D）或向右下（O）的路标字符数组。
注意到最后一行与最后一列各数只有一个出口，于是由b(n,m)开始向左逐个推出同行的b(n,j)(j=m-1,…,2,1)；向上逐个推出同列的b(i,m)(i=n-1,…,2,1)。
b(i,j)与stm(i,j) (i=n-1,…,2,1; j=m-1,…,2,1)的值由同一列其下面的整数b(i+1,j)与同一行其右边的整数b(i,j+1)或其右下方的b(i+1,j+1)的值决定：
设min=min(b(i+1,j+1),b(i,j+1),b(i+1,j)；
首先，作赋值min=b(i+1,j+1),stm(i,j)=”O”；
若b(i,j+1)<min，则min=b(i,j+1),stm(i,j)=”R”；
若b(i+1,j)<min, 则min=b(i+1,j),stm(i,j)=”D”。
然后赋值：b(i,j)=b(i,j)+min。
这样反推所得b(1,1)即为所求的最小路径数字和。
为了打印最小路径，利用c数组从上而下操作：
先打印a(1,1), i=1, j=1.
①若stm(i,j)=”R”，则j++，然后打印”-R-“与右边的整数a(i,j)。
②若stm(i,j)=”D”，则i++，然后打印”-D-“与下面的整数a(i,j)。
③若stm(i,j)=”O”，则i++,j++，然后打印”-O-“与斜右下的整数a(i,j)。
依次类推，直到打印到点a(n,m)。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main()
{
int m,n;
printf("请输入行数(n)和列数(m):");
scanf("%d%d",&n,&m);
int i=0;
int **randomArray = new int*[n];//随机数
for (i=0;i<n;i++)
{
randomArray[i] = new int[m];
}
int **weightData = new int*[n];
for (i=0;i<n;i++)
{
weightData[i] = new int[m];
}
char **storm = new char*[n];//存储方向
for (i=0;i<n;i++)
{
storm[i] = new char[m];
}
srand(time(NULL));
int row,col;
for (row=0;row<n;row++)
{
for (col=0;col<m;col++)
{
randomArray[row][col] = rand()%50+1;
weightData[row][col] = randomArray[row][col];
printf("%4d",randomArray[row][col]);
}
printf("\n");
}
// 第n行递推为边界条件
for (col=m-2;col>=0;col--)
{
weightData[n-1][col] = weightData[n-1][col] +weightData[n-1][col+1];
storm[n-1][col] = 'R';
}
// 第m列递推为边界条件
for (row=n-2;row>=0;row--)
{
weightData[row][m-1] = weightData[row][m-1] +weightData[row+1][m-1];
storm[row][m-1] = 'D';
}
//逆推求取最大值b(0,0)
int min;
for (row= n-2;row>=0;row--)
{
for (col = m-2;col>=0;col--)
{
min = weightData[row+1][col+1];
storm[row][col] = 'O';
if (min > weightData[row][col+1])
{
min = weightData[row][col+1];
storm[row][col] = 'R';
}
if (min > weightData[row+1][col])
{
min = weightData[row+1][col];
storm[row][col] = 'D';
}
weightData[row][col] = weightData[row][col] + min;
}
}
printf("\n最优路径数值和为:%d",weightData[0][0]);
printf("\n最优路径为:%2d",randomArray[0][0]);
row=0,col=0;
while((row < n-1 )||(col < m-1))
{
switch(storm[row][col])
{
case 'R':
{
col++;
printf("-(R-%d)",randomArray[row][col]);
}
break;
case 'D':
{
row++;
printf("-(D-%d)",randomArray[row][col]);
}
break;
case 'O':
{
col++;
row++;
printf("-(O-%d)",randomArray[row][col]);
}
break;
}
}
printf("\n");
for (i=0;i<n;i++)
{
delete []randomArray[i];
delete []weightData[i];
delete []storm[i];
}
delete []randomArray;
delete []weightData;
delete []storm;
randomArray = NULL;
weightData = NULL;
storm = NULL;
return 0;
}