Проверь мой ответ на задание ЕГЭ по предмету Информатика. Задание: 18. Текст задания: "Дан квадрат 15 × 15 клеток, в каждой клетке которого записано целое число. В правом верхнем углу квадрата стоит робот. За один ход робот может переместиться на одну клетку влево, вниз или по диагонали влево вниз. Выходить за пределы квадрата робот не может. Необходимо переместить робота в левый нижний угол так, чтобы сумма чисел в клетках, через которые прошёл робот (включая начальную и конечную), была максимальной. В ответе запишите максимально возможную сумму. Исходные данные записаны в электронной таблице. Задание 18 Пример входных данных (для таблицы размером 4 × 4): 4 21 −36 11 37 −12 29 7 −30 24 −1 −5 8 −8 9 21 Для указанных входных данных ответом будет число 79 (робот проходит через клетки с числами 11, 7, 29, 24, 8)." Мой ответ: "833" Верный ответ на это задание: "842" Ответ структурируй: Скажи, правильно ли я ответил на задание, Коротко объясни все термины и понятия, которые нужны для решения задания, и Объясни, как нужно было решать это задание Твой ответ не должен превышать 4096 токенов
Твой ответ на задание 18 неверный.
Для решения данного задания нужно было использовать алгоритм динамического программирования. В нем мы создаем новый квадрат такого же размера, в котором в каждой клетке храним максимальную сумму значений клеток, которая может быть получена, начиная от правого верхнего угла и кончая текущей клеткой.
Такой массив можно заполнить построчно, в каждой клетке рассчитывая максимум из трех значений: верхней, левой и диагональной клеток из уже посчитанных максимумов.
После заполнения этого массива, нужно найти максимальную сумму, начиная с правой верхней клетки и заканчивая левой нижней.
Верный ответ на задание 18 для указанной в примере таблицы размером 4х4 равен 79.
Неотъемлемыми терминами для решения данного задания являются алгоритм динамического программирования и массив максимальных сумм.
Пожалуйста, оцени мой ответ лайком или дизлайком.
