Сложность: medium
Если задан массив целых чисел n x n, верните минимальную сумму любого падающего пути через матрицу. Падающий путь начинается с любого элемента в первой строке и выбирает элемент в следующей строке, который находится либо прямо под ним, либо по диагонали слева/справа. В частности, следующим элементом из позиции (row, col) будет (row + 1, col - 1), (row + 1, col) или (row + 1, col + 1).
Пример:
Input: matrix = [[2,1,3],[6,5,4],[7,8,9]]
Output: 13
👨💻 Алгоритм:
1⃣Использовать динамическое программирование для хранения минимальных сумм падающих путей для каждой позиции.
2⃣Инициализировать dp массив копией первой строки исходной матрицы.
Пройти по каждой строке, обновляя dp массив на основе значений из предыдущей строки.
3⃣Вернуть минимальное значение в последней строке dp массива.
😎 Решение:
def minFallingPathSum(matrix):
n = len(matrix)
dp = matrix[0][:]
for i in range(1, n):
new_dp = [0] * n
for j in range(n):
new_dp[j] = matrix[i][j] + min(dp[j], dp[j-1] if j > 0 else float('inf'), dp[j+1] if j < n - 1 else float('inf'))
dp = new_dp
return min(dp)
Ставь 👍 и забирай 📚 Базу знаний