Квадрат разлинован на N×N клеток (1 < N < 17). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз  — в соседнюю

8 октября 2025
Программирование

Условие:

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

Решение:

Чтобы решить задачу о максимальном количестве монет, которые может собрать Робот, перемещаясь по квадрату размером N×N, мы можем использовать динамическое программирование. Давайте разберем решение шаг за шагом.

Шаг 1: Определение структуры данных

Создадим двумерный массив dp, где dp[i][j] будет хранить максимальное количество монет, которое Робот может собрать, достигнув клетки (i, j).

Шаг 2: Инициализация

Инициализируем массив dp следующим образом:
- dp[0][0] равно количеству монет в клетке (0, 0).
- Для первой строки (i = 0) и первого столбца (j = 0) мы можем заполнить значения, так как Робот может двигаться только вправо или вниз.

Шаг 3: Заполнение массива dp

Для каждой клетки (i, j) (где i и j от 0 до N-1) мы будем вычислять максимальное количество монет, которое можно собрать, используя следующие правила:
- Если Робот пришел из верхней клетки (i-1, j), то dp[i][j] может быть обновлено как dp[i][j] = dp[i-1][j] + монеты[i][j].
- Если Робот пришел из левой клетки (i, j-1), то dp[i][j] может быть обновлено как dp[i][j] = dp[i][j-1] + монеты[i][j].

Таким образом, мы можем записать:



dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + монеты[i][j]

Шаг 4: Итоговое значение

После заполнения массива dp, максимальное количество монет, которое Робот может собрать, будет находиться в правом нижнем углу массива, т.е. dp[N-1][N-1].

Пример кода

Вот пример кода на Python, который реализует описанный алгоритм:

Таким образом, мы можем использовать динамическое программирование для нахождения максимального количества монет, которые может собрать Робот, перемещаясь по квадрату размером N×N.