Игра: самый дешёвый маршрут по клеткам

В игре есть прямоугольная карта из клеток. В каждой клетке лежит «налог» — сколько монет игрок теряет, если зайдёт в эту клетку.

Игрок стартует в левом верхнем углу и хочет добраться в правый нижний. Из каждой клетки он умеет ходить только вправо или вниз.

Посчитайте, сколько монет он потеряет минимально возможным образом, если налог берётся и за стартовую клетку, и за финишную.

Формат ввода

В первой строке записаны два целых числа m и n — количество строк и столбцов карты.

Далее идут m строк по n целых чисел — налоги клеток.

Формат вывода

Выведите одно целое число — минимальную суммарную потерю монет на пути из (1,1) в (m,n).

Ограничения

• 1 ≤ m ≤ 200, 1 ≤ n ≤ 200
• 0 ≤ a[i][j] ≤ 1000
• Разрешённые ходы: только вправо и вниз

Пример

Ввод:

3 4
1 3 1 2
2 8 2 1
4 2 1 0

Вывод:

8

Ключевое наблюдение: попав в клетку (i,j), игрок мог прийти туда только из двух мест — (i-1,j) сверху или (i,j-1) слева. Значит, если мы знаем минимальную потерю до этих соседей, то для (i,j) достаточно выбрать меньшую и добавить налог текущей клетки.

Приём: динамическое программирование — считаем ответ «слева-направо, сверху-вниз», потому что зависимости всегда ведут в уже посчитанные клетки.

План:

• Заведи dp: dp[i][j] — минимальная сумма налогов на пути из (1,1) в (i,j), включая обе клетки.
• База: dp[0][0] = a[0][0].
• Первая строка: туда можно прийти только слева, значит dp[0][j] = dp[0][j-1] + a[0][j].
• Первый столбец: туда можно прийти только сверху, значит dp[i][0] = dp[i-1][0] + a[i][0].
• Остальные клетки:

dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + a[i][j].

• Ответ: dp[m-1][n-1].

Чтобы сэкономить память, можно хранить только одну строку dp (массив длины n): dp[j] — значение для текущей строки; при проходе слева направо dp[j] ещё хранит «сверху», а dp[j-1] уже обновлён и является «слева».

Сложность: O(m*n) по времени; по памяти O(m*n) или O(n) при оптимизации.

Частая ошибка: забыть, что налог берётся и за старт, и за финиш (поэтому dp[0][0] не 0, а a[0][0]), и отдельно аккуратно обработать первую строку/столбец (там нет выбора из двух направлений).