动态规划小问题

来源:百度知道 编辑:UC知道 时间:2024/05/11 22:15:30
用C 语言编程,求最短路径
**********************157******************************
******************63*******29*************************
***************15*****27*******135*****************
************2*******3********4***********5************
这个求最短路径是216,
这个图用二维存储如:
157 | 0 | 0 | 0 |
63 | 29 | 0 | 0 |
15 | 27 | 135 | 0 |
2 | 3 | 4 | 5 |
我遍了个程序看下怎么错了:
#include<stdio.h>
#include<mem.h>
main()
{int n,i,j;
scanf("%d",&n);
int a[n][n];
int b[n][n];
memset(a,0,sizeof(a));
for(i=0;i<n;i++)
for(j=0;j<=i;j++)
scanf("%d",&a[i][j]);
for(i=n-2;i>=0;i++)
for(j=0;j<i;j++)
{if(a[i+1][j]<=a[i+1][j+1])
{a[i][j]+=a[i+1][j];
b[i][j]=j;
}
else
{a[i][j]+=a[i+1][j+1];
b[i][j]=j+1;
}
}
printf("%d\n",a[0][0]);
while(1);
}
另外帮我改下,老师还要求打出路径(怎么走的).

f[i][j] = min(f[i-1][j],f[i-1][j-1]) + data[i][j]
把三角形抽象成这样,路径算的时候记录就是了。
157
63 29
15 27 135
2 3 4 5

ps.这是基础的的动态规划,可以参看“数字三角形”