Tam giác số (Pascal)

TAM GIÁC SỐ 

(Câu 4. Hội thi Tin Học Trẻ Phú Yên lần thứ XIX - năm 2016)

                             7
                         3       8
                     8      1       0
                  2     7        4       4
                4    5      2       6       5
Cho một tam giác gồm các số nguyên không âm (xem hình trên). Hãy viết chương trình tính tổng lớn nhất của các số nằm trên lộ trình từ đỉnh xuống:
- Tại mỗi bước đi, lộ trình có thể đi xuống phía bên trái hoặc xuống phía bên phải.
- Số hàng trong tam giác lớn hơn 1 và nhỏ hơn 100
- Các số nằm trong tam giác đều là số nguyên trong đoạn từ 0 đến 99.
Dữ liệu vào: câu4.inp
Dòng  đầu tiên chứa số dòng trong tam giác, các dòng tiếp theo chứa các số trên các hàng đó.
ví dụ:
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

Kết quả: cau4.out
Tổng lớn nhất các số ghi ra file cau4.out. trong ví dụ này là :30.
---Thuật toán---
- Sử dụng quy hoạch động để giải bài toán này
- Sử dụng mảng 2 chiều A để  lưu tam giác số, mảng F để thực hiện tính toán
F[1,1]=A[1,1]
F[i,1]=F[i-1,1]+A[i,1]
F[i,j] = max(F[i-1,j-1], F[i-1,j]) + A[i,j]

Đáp án:
uses crt;
Var A,F:array[1..100,1..100] of integer;
    i,j,n,max:integer;
    fi,fo:text;

    begin
    assign(fi,'tamgiacso.inp') ; reset(fi);
    assign(fo,'tamgiacso.out'); rewrite(fo);

 {doc du lieu tu tep vao mang 2 chieu A}
    readln(fi,N);
    readln(fi, a[1,1]);
    for i:=2 to N do
               begin
                 for j:=1 to i do read(fi,a[i,j]);
                 readln(fi);
               end;

  F[1,1]:=a[1,1];
  for i:=2 to N do f[i,1]:=F[i-1,1]+a[i,1];
  for i:=2 to N do
  for j:=2 to N do
  begin
  If F[i-1,j-1] > F[i-1,j] then F[i,j]:=  F[i-1,j-1] +a[i,j]
  else F[i,j]:= F[i-1,j]+a[i,j];
  end;


  Max:=f[n,1]; For j:= 2 to N do if max<F[n,j] then max:=F[n,j];
  write(fo,max);
  close(fi); close(fo);
    end.