Разбор

Пусть $a [i] [j]$ — исходная таблица. Обозначим через $d p [i] [j]$ максимальную сумму чисел на пути от любой клетки первой строки до клетки $(i, j)$ . Тогда

d p [i] [j] = ma x (d p [i - 1] [j - 1], d p [i - 1] [j], d p [i - 1] [j + 1]) + a [i] [j]

Для корректного вычисления значений в первом и последнем столбцах положим

d p [i] [0] = d p [i] [m + 1] = - \infty

Инициализируем первую строку массива $d p$ значениями первой строки таблицы $a$ :

d p [1] [i] = a [1] [i], 1 \leq i \leq m

Ответом на задачу будет максимальное значение в последней ( $n$ -ой) строке массива $d p$ .

Пример

Рассмотрим входной тест.

Реализация алгоритма

Объявим константу $M I N$ для хранения минимального значения, а также массивы $a$ и $d p$ .

#define MAX 202
#define MIN -2000000000
int a[MAX][MAX], dp[MAX][MAX];

Читаем входные данные. Верхний левый угол таблицы будем хранить в $a [1] [1]$ . Столбцы с номерами $0$ и $m + 1$ в массиве $d p$ заполним минимально возможным значением $M I N$ .

scanf("%d %d", &n, &m);
for (i = 1; i <= n; i++)
{
  dp[i][0] = dp[i][m + 1] = MIN;
  for (j = 1; j <= m; j++)
    scanf("%d", &a[i][j]);
}

Скопируем первую строку массива $a$ в массив $d p$ .

for (i = 1; i <= n; i++)
  dp[1][i] = a[1][i];

Пересчитаем максимальные суммы на путях от верхней строки до клетки $(i, j)$ и сохраним их в массиве $d p$ .

for (i = 2; i <= n; i++)
for (j = 1; j <= m; j++)
  dp[i][j] = max(max(dp[i - 1][j - 1], dp[i - 1][j]), 
                     dp[i - 1][j + 1]) + a[i][j];

Найдем наибольшее число в последней ( $n$ -ой) строке массива $d p$ .

res = MIN;
for (i = 1; i <= m; i++)
  if (dp[n][i] > res) res = dp[n][i];

Выводим ответ.

printf("%d\n", res);

Java реализация

import java.util.*;

public class Main
{
  static int a[][], dp[][];
  final static int MIN = -2000000000;
  
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    int m = con.nextInt();
    dp = new int[n+1][m+2];
    a = new int[n+1][m+2];
    
    for (int i = 1; i <= n; i++)
    {
      dp[i][0] = dp[i][m + 1] = MIN;
      for (int j = 1; j <= m; j++)
        a[i][j] = con.nextInt();;
    }
    
    for (int i = 1; i <= m; i++)
      dp[1][i] = a[1][i];
    
    for (int i = 2; i <= n; i++)
    for (int j = 1; j <= m; j++)
      dp[i][j] = Math.max(Math.max(dp[i - 1][j - 1], dp[i - 1][j]), dp[i - 1][j + 1]) + a[i][j];

    int res = MIN;
    for (int i = 1; i <= m; i++)
      if (dp[n][i] > res) res = dp[n][i];
    
    System.out.println(res);
    con.close();
  }
}