題意

寫(xiě)一個(gè)程序來(lái)查找從最高點(diǎn)到底部任意處結(jié)束的路徑，使路徑經(jīng)過(guò)數(shù)字的和最大。每一步可以走到左下方的點(diǎn)也可以到達(dá)右下方的點(diǎn)。

分析

這題我是用順推法來(lái)做的

按三角形的行劃分階段，若行數(shù)為 n，則可把問(wèn)題看做一個(gè)n-1個(gè)階段的決策問(wèn)題。先求第2行各元素到起點(diǎn)的最大和,再依次求出第3,4，5,......,.n-1,n到起點(diǎn)的最大和,最后找第n行的最大值設(shè)f[i,j]為第i行第j列上點(diǎn)到起點(diǎn)的最大和,狀態(tài)轉(zhuǎn)移方程為：

則 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.

轉(zhuǎn)載于:https://www.cnblogs.com/YYC-0304/p/9500180.html

總結(jié)

以上是生活随笔為你收集整理的数字三角形:顺推法（二维数组）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。