Минимальная сумма пути
Дана сетка высотой h и шириной w, заполненная целыми числами. Нужно найти маршрут из левого верхнего угла в правый нижний, при котором сумма чисел на пути будет минимальной. Разрешается двигаться только вправо или вниз.
3 | 2 | 1 | 3 |
1 | 9 | 2 | 3 |
9 | 1 | 5 | 4 |
Входные данные
Первая строка входных данных содержит два целых числа h и w (1 ≤ h, w ≤ 1000).
Следующие h строк содержат по w целых чисел, разделенных пробелами, , которые обозначают значения в сетке .
Выходные данные
Программа должна вывести минимально возможную сумму, которую можно получить, пройдя от левого верхнего до правого нижнего угла.
Примеры
Входные данные | Выходные данные |
|---|---|
3 4 3 2 1 3 1 9 2 3 9 1 5 4 | 15 |
Пояснение
Возможный путь: 3 → 2 → 1 → 2 → 3 → 4
Подсказка 1
В задаче динамического программирования состояние может быть представлено двумерным массивом.
Подсказка 2
В этом массиве можно хранить наилучшее решение для каждой координаты (d[r][c] означает лучший путь, позволяющий достичь строки r и столбца c).
Почему жадный подход не работает в данной задаче? Представьте, что вы всегда выбираете движение в направлении наименьшего элемента. Какую проблему это может вызвать?
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB