Решение: Максимальная и минимальная сумма
Квадрат разлинован на $N \times N$ клеток, где $1 < N < 30$. Исполнитель Робот перемещается из левой верхней клетки в правую нижнюю, выполняя команды «вправо» и «вниз». Между соседними клетками могут находиться внутренние стены, через которые Робот пройти не может. В каждой клетке лежит монета достоинством от 1 до 100; посетив клетку, Робот забирает монету, в том числе в начальной и конечной клетках.
Используя приложенный файл с электронной таблицей, определите максимальную и минимальную денежные суммы, которые может собрать Робот. В ответе укажите сначала максимальную сумму, затем минимальную.
Решение по шагам
4 шагаРазобьём квадрат на клетки и будем обрабатывать их слева направо и сверху вниз: Робот движется только вправо и вниз.
Для каждой клетки вычислим максимальную сумму на допустимом пути. Если в клетку можно прийти из нескольких клеток, выбираем наибольшую сумму среди разрешённых переходов и прибавляем стоимость монеты текущей клетки.
$$M_{i,j}=a_{i,j}+\max(M_{i-1,j},M_{i,j-1})$$Аналогично вычислим минимальную сумму, выбирая минимум среди разрешённых переходов.
$$m_{i,j}=a_{i,j}+\min(m_{i-1,j},m_{i,j-1})$$Переходы через внутренние стены не учитываются. Значения в правой нижней клетке являются соответственно максимальной и минимальной суммами.
Ввести максимальную и минимальную суммы, полученные в правой нижней клетке.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Не учитывать монеты в начальной или конечной клетке.
Разрешать проход через внутреннюю стену.
Использовать только один вариант оптимального пути вместо вычисления максимума и минимума.
Перепутать порядок чисел в ответе.