Tam giác (IOI 1994)

Tam giác (IOI 1994)

Cho một tam giác gồm các số nguyên không âm. Hãy tính tổng lớn nhất các số trên đường đi từ đỉnh tam giác xuống một điểm nào đó ở đáy tam giác nào đó. Tại mỗi ô ta chỉ có đi thẳng xuống, sang ô bên trái hoặc bên phải.

Hướng dẫn:

Mô tả các phần tử của tam giác số như một ma trận, A[i,j] là phần tử thứ j trên dòng i (với 1 ≤ i ≤ N và 1≤ j ≤ i). Có 2 ô có thể di chuyển đến ô (i,j) là ô (i–1, j–1) và ô (i–1,j). Gọi F(i, j) là tổng lớn nhất có thể có khi đi đến ô (i,j) ta có:
• 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]