Задача “Треугольник” (Рекуррентное соотношение с двумя параметрами)

Условие задачи: ссылка
Основная идея:  Данная задача является интерпретацией классической задачи “Черепашка”. Сначала давайте разберемся как будем хранить наш дивный треугольник в памяти. По условию задачи он выглядит так:
          7
        3   8
      8   1   0
    2   7   4   4
  4   5   2   6   5
Нам бы хотелось иметь более дружественный вид. Например в виде матрицы:
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Так уже лучше. Обычный двумерный массив int mas[n][n] (n – глубина дерева и количество элементов в нижней строке) подойдет. Но можно изловчиться и сделать “рванную” матрицу таким образом, что в первой строке будет один элемент, во второй  - два и т.д. Приведу реализацию функции считывания исходного треугольника.

1. void input()
2. {
3.   cin>>n;
4.   a.resize(n);
5.   for (int i=0;i<n;i++)
6.   {
7.     a[i].resize(i+1);
8.     for (int j=0;j<i+1;j++)
9.       cin>>a[i][j];
10.   }
11. }

Вот так наша матрица будет выглядеть в окне Watch в Visual Studio 2005/2008:
 

В данной вариации на лицо экономия памяти в 2 раза, но не нужно забывать про накладные расходы на создание этой самой рванной матрицы. Во время выполнение строчки 7 происходит перераспределение памяти, что влечет за собой увеличение времени работы программы. На самом деле увеличение времени будет малозаметным на ограничениях задачи. Но если у нас будут большие размерности, требующие до десятков мегабайтов, то стоит задуматься: “Стоит ли игра свеч?”
С представлением треугольника  в памяти разобрались. Теперь обсудим сам подход. Заведем еще одну рванную матрицу res, такую что в res[i][j] будем хранить максимальную сумму пути, который заканчивается в элементе a[i][j].
Что можно сказать с самого начала?
res[0][0] = a[0][0].
Также отметим важный факт, что в общем случае в элемент [i][j] можно попасть либо сверху [i-1][j], либо с севера-запада [i-1][j-1]. Элементы, находящиеся на главной диагонали и в первом столбце являются исключением. Рассмотрим утверждение для элемента, не находящегося на главной диагонали и в первом столбце:
“Элемент [i][j] является продолжением одного из путей, заканчивающегося в элементе [i-1][j] или в  [i-1][j-1], и для того, чтобы найти максимальный путь, заканчивающийся в элементе [i][j] мы должны выбрать максимальную суммы из: res[i-1][j] + a[i][j] и res[i][j-1] + a[i][j]”
Частные решения для элементов первого столбца и главной диагонали вытекают из общего решения. На основе всего сказано можно сделать рекуррентное соотношение для общего случая.
Исходный код: здесь
P.S: Данная задача была представлена на IOI’94. Но обольщаться не стоит. Как точно было подмечено в книге Кирюхина и Окулова, что даже в те времена она носила утешительный характер.