Question

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

Answer 1

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

Answer 2

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

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.