本文主要是介绍数字三角形:顺推法（二维数组），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意
写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。
分析
这题我是用顺推法来做的
按三角形的行划分阶段，若行数为 n，则可把问题看做一个n-1个阶段的决策问题。先求第2行各元素到起点的最大和,再依次求出第3,4，5,......,.n-1,n到起点的最大和,最后找第n行的最大值设f[i,j]为第i行第j列上点到起点的最大和,状态转移方程为：
则 f[1，1]=a[1,1];
f[i，1]=a[i,1]+f[i-1,1];
f[i，j]=max{a[i,j]+f[i-1,j-1],a[i,j]+f[i-1,j]} 2<=j<=i
max(f[n,1],f[n,2],.......,f[n,n]}即为所求。
var
n,i,j,maxsum:longint;
a,f:array[1..1000,1..1000]of longint;
begin
readln(n);
for i:=1 to n do
for j:=1 to i do
read(a[i,j]);
f[1,1]:=a[1,1];
for i:=2 to n do
begin
f[i,1]:=a[i,1]+f[i-1,1];
for j:=2 to i do
if f[i-1,j-1]>f[i-1,j] then f[i,j]:=a[i,j]+f[i-1,j-1] else
f[i,j]:=a[i,j]+f[i-1,j];
end;
maxsum:=0;
for i:=1 to n do
if f[n,i]>maxsum then maxsum:=f[n,i];
write(maxsum);
end.
这篇关于数字三角形:顺推法（二维数组）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
