codevs动态规划 数字三角形

如图所示的数字三角形，从顶部出发，在每一结点可以选择向左走或得向右走，一直走到底层，要求找出一条路径，使路径上的值最大。

分析：超菜的一道倒推题（完全无脑==）

动态转移方程：f[i,j]:=max(f[i+1,j],f[i+1,j+1])+f[i,j];

const   maxn=100; var   a:array[1..maxn,1..maxn] of longint;   i,j,n:longint; function max(x,y:longint):longint; begin   if x<y then exit(y)   else exit(x); end; begin   readln(n);   for i:=1 to n do     for j:=1 to i do       if j<i then read(a[i,j])       else readln(a[i,j]);   for i:=n-1 downto 1 do     for j:=1 to i do       a[i,j]:=a[i,j]+max(a[i+1,j],a[i+1,j+1]);   writeln(a[1,1]); end.