Уровень сложности: Средняя (Medium)
Теги: Динамическое программирование, Матрица, Жадные алгоритмы (не подходят!)
Условие задачи
Дана сетка grid размером m x n, заполненная неотрицательными целыми числами.
Найдите путь из левого верхнего угла в правый нижний угол, двигаясь только вправо или вниз, такой, чтобы сумма чисел вдоль пути была минимальной.
Верните эту минимальную сумму.
Пример 1:
Ввод: grid = [[1,3,1],[1,5,1],[4,2,1]]
Вывод: 7
Объяснение: Путь 1 → 3 → 1 → 1 → 1 имеет сумму 7 (но это НЕ минимальный!).
Минимальный путь: 1 → 1 → 1 → 1 → 1 → сумма = 7? Нет!
Правильный путь: 1 → 1 → 4 → 2 → 1? Нет!
Фактически: 1 → 1 → 5 → 1 → 1 — тоже не то.
А вот: 1 → 3 → 1 → 1 → 1 = 7
ИЛИ: 1 → 1 → 1 → 1 → 1 = **1+1+1+1+1 = 5**? Но такой путь невозможен!
Давайте посчитаем правильно:
Путь: (0,0) → (1,0) → (1,1) → (1,2) → (2,2)
= 1 + 1 + 5 + 1 + 1 = **9**
А вот оптимальный:
(0,0) → (0,1) → (0,2) → (1,2) → (2,2)
= 1 + 3 + 1 + 1 + 1 = **7**
Но есть ещё лучше:
(0,0) → (1,0) → (2,0) → (2,1) → (2,2)
= 1 + 1 + 4 + 2 + 1 = **9**
А вот **настоящий оптимальный**:
(0,0) → (0,1) → (1,1) → (2,1) → (2,2)
= 1 + 3 + 5 + 2 + 1 = **12** — хуже!
Подождите… Давайте пересчитаем по решению:
На самом деле, **минимальный путь**:
(0,0) → (1,0) → (1,1) → (1,2) → (2,2) = 1+1+5+1+1 = **9**?
Нет!
Правильный ответ — **7**, и путь:
**1 → 3 → 1 → 1 → 1** — это (0,0)→(0,1)→(0,2)→(1,2)→(2,2) = 1+3+1+1+1 = **7**
Да, это действительно минимальный.
Пример 2:
Ввод: grid = [[1,2,3],[4,5,6]]
Вывод: 12
Путь: 1 → 2 → 3 → 6 = 12
(или 1 → 4 → 5 → 6 = 16 — хуже)
Анализ задачи
На первый взгляд может показаться, что можно использовать жадный подход: на каждом шаге выбирать меньшее из двух соседей (вправо или вниз).
Но это не сработает!
💡 Пример, где жадность ломается:12[[1, 2],[1, 1]]Жадный путь: 1 → 2 → 1 = 4
Оптимальный: 1 → 1 → 1 = 3
Значит, нужно учитывать всю картину — и тут на помощь приходит динамическое программирование (DP).
Идея DP:
- dp[i][j] = минимальная сумма, чтобы добраться до клетки (i, j)
- Переход:
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]) - База:dp[0][0] = grid[0][0]
Первая строка: можно прийти только слева → dp[0][j] = dp[0][j-1] + grid[0][j]
Первый столбец: только сверху → dp[i][0] = dp[i-1][0] + grid[i][0]
Решение на Java
Комментарии к коду:
- Мы не проверяем границы внутри основного цикла, потому что обработали первую строку и столбец отдельно.
- Math.min(dp[i-1][j], dp[i][j-1]) — выбираем лучший путь (сверху или слева).
- Результат — в правом нижнем углу: dp[m-1][n-1].
Объяснение «словами пятилетнего»
Представь, ты идёшь по парку, где на каждой плитке лежит монетка (или карамелька!).
Некоторые плитки — с одной монеткой, другие — с тремя.
Ты начинаешь в верхнем левом углу и хочешь дойти до нижнего правого, но ходить можно только вправо или вниз.
Твоя цель — собрать как можно меньше монеток (может, ты не любишь монетки? 😄).
На каждой плитке ты думаешь:
«Откуда лучше прийти — сверху или слева? Оттуда, где у меня меньше монеток!»
Ты запоминаешь, сколько монеток у тебя будет, если дойдёшь до этой плитки.
И так, шаг за шагом, ты находишь самый "бедный" путь до конца!
Вот это и делает наша программа 😊
Заключение
Пример, рассмотренный в статье, можно найти по адресу:
https://github.com/ShkrylAndrei/leetcode/blob/main/src/main/java/info/shkryl/task64_minimumPathSum/Solution.java