Dynamic Programming - Minimum Falling Path Sum

Given n x n integer matrix, return the minimum sum of any falling path through the matrix. A falling path starts at any element in the first row and chooses the element in the next row that is directly below or diagonally adjacent.

Input: [[2,1,3],[6,5,4],[7,8,9]] → Output: 13

Input: [[-19,57],[-40,-5]] → Output: -59

DP: for each cell (i,j), the minimum falling path is min of the three cells above it (i-1, j-1), (i-1, j), (i-1, j+1) plus matrix[i][j].

Process row by row in-place.
For each row i from 1 to n-1:
For each col j: matrix[i][j] += min(matrix[i-1][j], matrix[i-1][j-1 if valid], matrix[i-1][j+1 if valid]).
Return min of last row.

class Solution { public int minFallingPathSum(int[][] matrix) { int n = matrix.length; for (int i = 1; i < n; i++) { for (int j = 0; j < n; j++) { int best = matrix[i-1][j]; if (j > 0) best = Math.min(best, matrix[i-1][j-1]); if (j < n-1) best = Math.min(best, matrix[i-1][j+1]); matrix[i][j] += best; } } int min = Integer.MAX_VALUE; for (int v : matrix[n-1]) min = Math.min(min, v); return min; } }

Time Complexity: O(N^2)
Space Complexity: O(1)