Треугольник
http://acm.pku.edu.cn/JudgeOnline/problem?id=1163

7
3   8
8   1   0
2   7   4   4
4   5   2   6   5
Треугольник из чисел

   На рисунке выше изображен треугольник из чисел. Напишите программу, которая вычисляет наибольшую сумму чисел, расположенных на пути, начинающемся в верхней точке и заканчивающемся на основании треугольника.

   Каждый шаг на пути может осуществляться вниз по диагонали влево, или вниз по диагонали вправо.

   Входные данные

   Первым числом входных данных является количество строк в треугольнике. Далее следует соответствующее число строк с описанием самого треугольника. Число строк в треугольнике больше 1 и меньше или равно 100. Треугольник составлен из целых чисел от 0 до 99.

   Выходные данные

   Выведите единственное число - искомую наибольшую сумму.

   Пример входных данных

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

   Пример выходных данных

30

   Анализ условия и обсуждение идеи решения

   Задача является "утешительной". Это типичная задача на метод динамического программирования. Рекомендуется для приведенного примера найти путь вручную и после этого составить соответствующую программу ученикам самостоятельно на основании найденных рекуррентных отношений для созданной динамической таблицы.

   Пример решения на Pascal:

var n, i, j: longint;
    a, f: array[1 .. 101, 1 .. 101] of longint;

begin
  readln(n);
  for i := 1 to n do for j := 1 to i do read(a[i, j]);
  fillchar(f, sizeof(f), 0);
  for i := n downto 1 do
    for j := 1 to i do
    if f[i + 1, j] > f[i + 1, j + 1] then f[i, j] := f[i + 1, j] + a[i, j]
    else f[i, j] := f[i + 1, j + 1] + a[i, j];
  writeln(f[1, 1]);
end.

Пример решения на С++:

#include<stdio.h>

int main()
{
int i, j, a[101][101], n;

while( scanf( "%d", &n ) != EOF )
{
    for( i = 0; i < n; i++ )
    for( j = 0; j <= i; j++ )
     scanf( "%d", &a[i][j] );

    for( i = n - 1; i >= 0; i-- )
    {
     for( j = 0; j < i; j++ )
     {
      if( a[i][j] > a[i][j + 1] )
       a[i - 1][j] += a[i][j];
      else
       a[i - 1][j] += a[i][j + 1];
     }
    }

    printf( "%d\n", a[0][0] );
}
return 0;
}