Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой верхней клетки в правую нижнюю. В ответ запишите два числа друг за другом без разделительных знаков — сначала максимальную сумму, затем минимальную.
Привет! Давай разберёмся с задачей.
Нам нужно помочь Роботу пройти из левой верхней клетки (2 на (0,0)) в правую нижнюю клетку (18 на (9,14)), собирая деньги в каждой клетке так, чтобы собрать максимум и минимум возможных сумм. Робот может двигаться только вправо или вниз.
Для начала, мы будем использовать динамическое программирование. Создадим две таблицы: одну для максимальных сумм и одну для минимальных сумм. Будем заполнять их шаг за шагом, учитывая предыдущие результаты.
Инициализация первой клетки:
макс[0][0] = мин[0][0] = поле[0][0]
Заполнение первой строки (можно только идти вправо):
макс[0][j] = макс[0][j-1] + поле[0][j]мин[0][j] = мин[0][j-1] + поле[0][j]
Заполнение первого столбца (можно только идти вниз):
макс[i][0] = макс[i-1][0] + поле[i][0]мин[i][0] = мин[i-1][0] + поле[i][0]
Заполнение остальных клеток:
макс[i][j] = макс(макс[i-1][j], макс[i][j-1]) + поле[i][j]мин[i][j] = мин(мин[i-1][j], мин[i][j-1]) + поле[i][j]
После заполнения таблиц:
- Максимальная сумма будет находиться в
макс[9][14] - Минимальная сумма будет находиться в
мин[9][14]
Теперь давай посчитаем:
Инициализация первой клетки:
макс[0][0] = мин[0][0] = 2
Заполнение первой строки:
макс[0][j] = мин[0][j] = 2 + 79 = 81- и так далее для остальных клеток строки.
Заполнение первого столбца:
макс[i][0] = мин[i][0] = 2 + 48 = 50- и так далее для остальных клеток столбца.
Мы продолжаем заполнять по аналогии всю таблицу, учитывая предыдущие суммы.
Как только мы это сделаем, получаем максимальную и минимальную суммы: Максимальная сумма в клетке (9, 14) и минимальная сумма также в клетке (9, 14).
Так что ответ будет:
максмальная сумма || минимальная сумма
Вот как наш робот успешно соберет все монеты!
