Код Senior Динамическое программирование обновлено
Минимальная сумма пути в сетке
Условие
Ходить можно только вправо и вниз. Минимальная сумма чисел на пути из левого верхнего в правый нижний угол.
Примеры
minPathSum([[1, 3, 1], [1, 5, 1], [4, 2, 1]]) // 7
minPathSum([[1, 2], [1, 1]]) // 3
minPathSum([]) // 0
Как подойти
Та же свёртка до одной строки, что и в подсчёте путей, но с минимумом вместо суммы. Понимание, что «старое значение ячейки - это сверху, а соседнее слева - уже новое», отличает механическое применение от осознанного.
Подсказки: 2
- В клетку приходят сверху и слева - берём минимум.
- Хватит одной строки: row[c] до обновления хранит значение сверху, row[c-1] - слева.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.