Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой верхней клетки в правую нижнюю. В ответ запишите два числа друг за другом без…

Привет! Давай разберёмся с задачей.

Нам нужно помочь Роботу пройти из левой верхней клетки (2 на (0,0)) в правую нижнюю клетку (18 на (9,14)), собирая деньги в каждой клетке так, чтобы собрать максимум и минимум возможных сумм. Робот может двигаться только вправо или вниз.

Для начала, мы будем использовать динамическое программирование. Создадим две таблицы: одну для максимальных сумм и одну для минимальных сумм. Будем заполнять их шаг за шагом, учитывая предыдущие результаты.

1. Инициализация первой клетки:

   • макс[0][0] = мин[0][0] = поле[0][0]

2. Заполнение первой строки (можно только идти вправо):

   • макс[0][j] = макс[0][j-1] + поле[0][j]
   • мин[0][j] = мин[0][j-1] + поле[0][j]

3. Заполнение первого столбца (можно только идти вниз):

   • макс[i][0] = макс[i-1][0] + поле[i][0]
   • мин[i][0] = мин[i-1][0] + поле[i][0]

4. Заполнение остальных клеток:

   • макс[i][j] = макс(макс[i-1][j], макс[i][j-1]) + поле[i][j]
   • мин[i][j] = мин(мин[i-1][j], мин[i][j-1]) + поле[i][j]

После заполнения таблиц:

• Максимальная сумма будет находиться в макс[9][14]
• Минимальная сумма будет находиться в мин[9][14]

Теперь давай посчитаем:

1. Инициализация первой клетки:

   • макс[0][0] = мин[0][0] = 2

2. Заполнение первой строки:

   • макс[0][j] = мин[0][j] = 2 + 79 = 81
   • и так далее для остальных клеток строки.

3. Заполнение первого столбца:

   • макс[i][0] = мин[i][0] = 2 + 48 = 50
   • и так далее для остальных клеток столбца.

Мы продолжаем заполнять по аналогии всю таблицу, учитывая предыдущие суммы.

Как только мы это сделаем, получаем максимальную и минимальную суммы: Максимальная сумма в клетке (9, 14) и минимальная сумма также в клетке (9, 14).

Так что ответ будет: максмальная сумма || минимальная сумма

Вот как наш робот успешно соберет все монеты!