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

Держи на языке программирования python, может поймешь принцип работы, если не понял обращайся.

Для решения данной задачи можно использовать алгоритм динамического программирования.

1. Создадим два двумерных массива: max_sum и min_sum, размерностью (N+1)x(N+1), где N - размер квадрата.

2. Заполним массивы начальными значениями. В каждой клетке (i, j) max_sum[i][j] и min_sum[i][j] будет храниться максимальная и минимальная сумма монет, которую можно собрать, пройдя от верхней левой клетки до клетки (i, j).

3. Начинаем заполнять массивы построчно.
- В клетке (1, 1) max_sum[1][1] = min_sum[1][1] = значение этой клетки.
- Заполняем первую строку и первый столбец: max_sum[1][j] = max_sum[1][j-1] + значение клетки (1, j), min_sum[1][j] = min_sum[1][j-1] + значение клетки (1, j); max_sum[i][1] = max_sum[i-1][1] + значение клетки (i, 1), min_sum[i][1] = min_sum[i-1][1] + значение клетки (i, 1), где i и j больше 1 и меньше или равны N.
- Для каждой оставшейся клетки (i, j) вычисляем максимальную и минимальную суммы: max_sum[i][j] = max(max_sum[i-1][j], max_sum[i][j-1]) + значение клетки (i, j), min_sum[i][j] = min(min_sum[i-1][j], min_sum[i][j-1]) + значение клетки (i, j).

4. В конечной клетке (N, N) будет находиться максимальная и минимальная сумма, которую можно собрать.

5. В ответе укажите два числа: max_sum[N][N] и min_sum[N][N].

Пример решения задачи:

Пусть дан следующий квадрат размером 4x4:
1 5 9 11
3 8 2 5
4 1 7 3
2 4 6 7

1. Создаем двумерные массивы max_sum и min_sum размером 5x5:

0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

2. Заполняем массивы начальными значениями:

max_sum[1][1] = min_sum[1][1] = 1
max_sum[1][2] = min_sum[1][2] = 6
max_sum[1][3] = min_sum[1][3] = 15
max_sum[1][4] = min_sum[1][4] = 26
max_sum[2][1] = min_sum[2][1] = 4
max_sum[3][1] = min_sum[3][1] = 8
max_sum[4][1] = min_sum[4][1] = 12

3. Заполняем оставшиеся клетки:

max_sum[2][2] = max(max_sum[1][2], max_sum[2][1]) + 5 = max(6, 4) + 5 = 11 + 5 = 16
min_sum[2][2] = min(min_sum[1][2], min_sum[2][1]) + 5 = min(6, 4) + 5 = 4 + 5 = 9

max_sum[2][3] = max(max_sum[1][3], max_sum[2][2]) + 9 = max(15, 16) + 9 = 16 + 9 = 25
min_sum[2][3] = min(min_sum[1][3], min_sum[2][2]) + 9 = min(15, 9) + 9 = 9 + 9 = 18

max_sum[2][4] = max(max_sum[1][4], max_sum[2][3]) + 11 = max(26, 25) + 11 = 26 + 11 = 37
min_sum[2][4] = min(min_sum[1][4], min_sum[2][3]) + 11 = min(26, 18) + 11 = 18 + 11 = 29

max_sum[3][2] = max(max_sum[2][2], max_sum[3][1]) + 2 = max(16, 8) + 2 = 16 + 2 = 18
min_sum[3][2] = min(min_sum[2][2], min_sum[3][1]) + 2 = min(9, 8) + 2 = 8 + 2 = 10

...

max_sum[4][4] = max(max_sum[3][4], max_sum[4][3]) + 7 = max(32, 37) + 7 = 37 + 7 = 44
min_sum[4][4] = min(min_sum[3][4], min_sum[4][3]) + 7 = min(23, 29) + 7 = 23 + 7 = 30

4. В конечной клетке (4, 4) будет находиться максимальная и минимальная сумма, которую можно собрать:

max_sum[4][4] = 44
min_sum[4][4] = 30

Таким образом, максимальная сумма, которую может собрать Робот, составляет 44, а минимальная - 30.