Максимальная и минимальная сумма
Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). В каждой клетке лежит монета достоинством от 1 до 100. Робот начинает движение из левой верхней клетки и может перемещаться только вправо или вниз, если между соседними клетками нет стены. Посетив клетку, робот забирает монету, в том числе в начальной и конечной клетках маршрута. В клетках, которые справа и снизу ограничены стенами, робот прекращает движение; накопленная сумма считается итоговой. Определите максимальную и минимальную суммы среди всех возможных маршрутов. Исходные данные находятся в прилагаемом файле: электронная таблица содержит значения монет, а утолщённые линии обозначают внутренние и внешние стены.
Условие как в банке ФИПИ — открыть и сверить
| ||||||||||||||||||||||
| | ||||||||||||||||||||||
Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.
1Мягкая — с чего смотретьуровень 1 из 3
Для каждой клетки храните максимальную и минимальную сумму, которую можно набрать при попадании в эту клетку.
2Наводящая — какие числа считатьуровень 2 из 3
При переходе в клетку прибавляйте её стоимость к максимуму или минимуму из достижимых соседних клеток сверху и слева. Переход через стену запрещён.
3Прямая — фактически решениеуровень 3 из 3
Для каждой клетки $(i,j)$ вычисляйте $\mathrm{maxSum}[i,j] = a[i,j] + \max(\mathrm{maxSum}[i-1,j],\mathrm{maxSum}[i,j-1])$ и аналогично минимум. В итоговый список включите значения в каждой клетке, ограниченной стенами справа и снизу.