Решение: Максимальный и минимальный путь
Квадрат разлинован на $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})$$Для всех клеток, ограниченных стенами справа и снизу, выбираем наибольшее значение из таблицы максимумов и наименьшее значение из таблицы минимумов.
$$S_{\max}=\max_{(i,j)\in F} M_{i,j},\quad S_{\min}=\min_{(i,j)\in F} m_{i,j}$$Числа определяются по данным приложенного файла.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Не учитывают монету в начальной клетке.
Не учитывают монету в конечной клетке.
Разрешают переход через внутреннюю стену.
Ищут максимум и минимум только для правой нижней клетки, не проверяя остальные конечные клетки.
Путают максимальную и минимальную суммы в итоговом ответе.