Проверь мой ответ на задание ЕГЭ по предмету Информатика. Задание: 18. Текст задания: "Дан квадрат 15 × 15 клеток, в каждой клетке которого записано целое число. В левом нижнем углу квадрата стоит ладья. За один ход ладья может переместиться в пределах квадрата на любое количество клеток вправо или вверх (влево и вниз ладья ходить не может). Необходимо переместить ладью из левого нижнего угла в правый верхний и найти максимальную и минимальную сумму чисел в клетках, в которых ладья останавливалась (включая начальную и конечную). В ответе запишите сначала минимальную, а затем максимальную сумму без разделителей. 18.xlsx ЛИСТ 8 (Переключение между листами находится внизу Exel)" Мой ответ: "8432112" Верный ответ на это задание: "1161974" Ответ структурируй: Скажи, правильно ли я ответил на задание, Коротко объясни все термины и понятия, которые нужны для решения задания, и Объясни, как нужно было решать это задание Твой ответ не должен превышать 4096 токенов

Ты ответил неверно на задание.

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

Динамическое программирование - это метод решения задач, основанный на разбиении исходной задачи на более простые подзадачи, решение которых сохраняется и используется для решения более сложной исходной задачи.

Итак, для решения задачи нужно создать вспомогательную таблицу размером 15x15, в которой будут храниться минимальная и максимальная суммы чисел на пути ладьи из левого нижнего угла в каждую из клеток. В ячейку (i, j) таблицы записывается сумма чисел в клетках, которые находятся на пути ладьи от левого нижнего угла до клетки (i, j).

Для заполнения таблицы значениями нужно использовать следующий рекуррентный соотношения:

min_sum[i][j] = min(min_sum[i-1][j], min_sum[i][j-1]) + a[i][j] max_sum[i][j] = max(max_sum[i-1][j], max_sum[i][j-1]) + a[i][j]

где a[i][j] - число в клетке (i, j) изначальной таблицы.

После того, как таблица будет заполнена, ответом на задачу будет значение в ячейке таблицы (15, 15).

Минимальная сумма чисел на пути ладьи будет равна значению min_sum[15][15], а максимальная - max_sum[15][15].

Попроси меня оценить твой ответ!