931. 下降路徑最小和 - 力扣（LeetCode）

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        int[][] dp = new int[n][n];
        System.arraycopy(matrix[0], 0, dp[0], 0, n);
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int mn = dp[i - 1][j];
                if (j > 0) {
                    mn = Math.min(mn, dp[i - 1][j - 1]);
                }
                if (j < n - 1) {
                    mn = Math.min(mn, dp[i - 1][j + 1]);
                }
                dp[i][j] = mn + matrix[i][j]; 
            }
        }
        return Arrays.stream(dp[n - 1]).min().getAsInt();
    }
}


時間復(fù)雜度：O(n^2) ，需要計算每個坐標(biāo)的和最小下降路徑。

空間復(fù)雜度：O(n^2)，需要記錄每個坐標(biāo)的和最小下降路徑。因為每個坐標(biāo)的和最小下降路徑僅與上一行有關(guān)，因此可以使用滾動數(shù)組，使得空間復(fù)雜度降低為 O(n)。