Задача: 931. Minimum Falling Path Sum
Сложность: 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 массива.

😎 Решение:

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        int[] dp = matrix[0].clone();
        
        for (int i = 1; i < n; i++) {
            int[] newDp = new int[n];
            for (int j = 0; j < n; j++) {
                newDp[j] = matrix[i][j] + Math.min(dp[j], Math.min(j > 0 ? dp[j - 1] : Integer.MAX_VALUE, j < n - 1 ? dp[j + 1] : Integer.MAX_VALUE));
            }
            dp = newDp;
        }
        
        int minSum = Integer.MAX_VALUE;
        for (int sum : dp) {
            minSum = Math.min(minSum, sum);
        }
        return minSum;
    }
}

Ставь 👍 и забирай 📚 Базу знаний