Самый дешевый путь в матрице

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

Оптимальное решение нашей сегодняшней задачи достигается как раз с помощью этого приема: чтобы найти самый дешевый путь от левого вернего элемент матрицы к правому нижнему, нам нужно найти самые дешевые пути к соседу сверху и соседу слева. Тот же подход справедлив и для этих самых соседних элементов. Таким образом, процесс решения задачки сводится к поиску самого дешевого пути к каждому элементу матрицы, основываясь на ранее найденных дешевых путях к соседним элементам🙂

Сложность: 🟠 Cредняя

ℹ️ Описание

Вам дана матрицы m * n. Значение каждой ячейки — стоимость перехода в эту ячейку из соседних. Переходить можно либо в ячейку справа, либо в ячейку снизу.

Напишите функцию, которая вернет стоимость самого дешевого пути от левого верхнего угла матрицы к правому нижнему.

⚠️ Ограничения

🔹Высота и ширина матрицы заданы в диапазоне от 1 до 200
🔹Значения ячеек матрицы заданы в диапазоне от 0 до 200


1️⃣ Пример

Входящие данные: [[1,3,1],[1,5,1],[4,2,1]]
Ответ: 7

Самый дешевый путь:
🔹Перемещаемся на 3 ячейки вправо (1+3+1)
🔹Спускаемся на две ячейки вниз (1+1)
Суммарный путь — 7.


2️⃣ Пример

Входящие данные: [[1,2,3],[4,5,6]]
Ответ: 12

Самый дешевый путь:
🔹Перемещаемся на 3 ячейки вправо (1+2+3)
🔹Спускаемся на одну ячейку вниз (6)
Суммарный путь — 12.

3️⃣ Пример

Входящие данные: [[1,12,1],[1,5,1],[1,9,1]]
Ответ: 9

Самый дешевый путь:
🔹Спускаемся на одну ячейку вниз (1+1)
🔹Перемещаемся на 2 ячейки вправо (5+1)
🔹Спускаемся на одну ячейку вниз (1)
Суммарный путь — 9.


✅ Решение

В этой задаче понятное брутфорс решение — проверить все возможные пути и найти минимум. Но это тот случай, когда реализовать брутфорс оказалось сложнее чем оптимальное. Но, все же, я решил приложить и такой вариант, ведь на собеседовании почти наверняка он придет первым в голову. Для поиска всех возможных путей я преобразовал матрицу в граф и сделал обход в глубину. Подробнее по ссылкам — go и typescript.

Теперь подробнее про оптимальное решение. Как я писал в самом начале, мы разбиваем задачу на более маленькие — поиск самого дешевого пути к каждому из элементов матрицы, основываясь на найденных дешевых путях к элементу слева и сверху. Для экономии памяти, мы будем заменять in-place значения ячеек в исходной матрице с цены перехода в эту ячейку, на стоимость самого дешевого пути к этой ячейке от левого верхнего угла.

🔘 Запускаем стандартный обход матрицы по i, j

🔘 При i = 0 && j = 0 (левый верхний угол) стоимость пути равна исходному значению ячейки.

🔘 При i = 0 (элементы верхней строчки) стоимость пути равна сумме измененого значению слева (стоимость пути к левому элементу) с оригинальным значением текущего элемента. Помним, что перемещаться мы можем только вправо и вниз, так что попасть в элемент первой строчки матрицы мы можем только из соседнего элемента слева.

🔘 При j = 0 (элементы первой колонки) стоимость пути равна сумме измененого значению сверху (стоимость пути к верхнему элементу) с оригинальным значением текущего элемента. Так же как и в предыдущем условии, в элемент первой колонки матрицы мы можем попасть только из соседнего элемента сверху.

🔘 Для всех остальных элементов матрицы стоимость пути равна сумме текущего значения элемента и минимального значения из двух: измененное значение сверху и измененное значение слева. Таким образом мы находим самый дешевый путь к текущему элементу матрицы.

🔘 После того как мы полностью промутируем матрицу в правом нижнем элементе матрицы окажется искомое нами значение.

Посмотреть реализацию в блоге

🅾️ Оценка сложности

По времени

Для того, чтобы найти самый дешевый путь нам достаточно один раз пройтись по всем элементам матрицы. Сложность - O(m*n).

По памяти

Все промежуточные результаты мы сразу заносим в оригинальную матрицы, т.е. делаем изменения in-place без выделения дополнительной памяти. Сложность по памяти константная — O(1).

#matrix #medium