Квадрат разлинован на N×N клеток (1 < N < 17). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. При попытке выхода за границу квадрата Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота. Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой верхней клетки в правую нижнюю. В ответе укажите два числа – сначала максимальную сумму, затем минимальную. Исходные данные представляют собой электронную таблицу размером N×N, каждая ячейка которой соответствует клетке квадрата.

Конкретные два числа определить нельзя: в условии отсутствуют значения монет из таблицы N×N. Ответ полностью зависит от содержимого каждой клетки.

Решение выполняется динамическим программированием. Робот может попасть в клетку (i, j) только сверху или слева, поэтому для каждой клетки достаточно хранить две величины:

• максимальную сумму, с которой в неё можно прийти;

• минимальную сумму, с которой в неё можно прийти.

Пусть a[i][j] — монета в клетке.

Для начальной клетки:

maxSum[0][0] = minSum[0][0] = a[0][0]

Для первой строки и первого столбца путь единственный, поэтому суммы просто накапливаются:

maxSum[0][j] = maxSum[0][j-1] + a[0][j]
minSum[0][j] = minSum[0][j-1] + a[0][j]

maxSum[i][0] = maxSum[i-1][0] + a[i][0]
minSum[i][0] = minSum[i-1][0] + a[i][0]

Для остальных клеток:

maxSum[i][j] = a[i][j] + max(maxSum[i-1][j], maxSum[i][j-1])
minSum[i][j] = a[i][j] + min(minSum[i-1][j], minSum[i][j-1])

Искомые значения находятся в правой нижней клетке:

максимальная сумма = maxSum[N-1][N-1]
минимальная сумма   = minSum[N-1][N-1]

Например, на Python вычисление выглядит так:

Python
Запустить
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]

mx = [[0] * n for _ in range(n)]
mn = [[0] * n for _ in range(n)]

mx[0][0] = mn[0][0] = a[0][0]

for j in range(1, n):
    mx[0][j] = mx[0][j - 1] + a[0][j]
    mn[0][j] = mn[0][j - 1] + a[0][j]

for i in range(1, n):
    mx[i][0] = mx[i - 1][0] + a[i][0]
    mn[i][0] = mn[i - 1][0] + a[i][0]

for i in range(1, n):
    for j in range(1, n):
        mx[i][j] = a[i][j] + max(mx[i - 1][j], mx[i][j - 1])
        mn[i][j] = a[i][j] + min(mn[i - 1][j], mn[i][j - 1])

print(mx[n - 1][n - 1], mn[n - 1][n - 1])

Без самой электронной таблицы численный ответ указать невозможно.