931. Minimum Falling Path Sum

• 행렬이 주어졌을 때 가장 위쪽 행으로 부터 가장 아래 행까지 탐색한다. 이 때 탐색한 경로의 숫자 합 중 가장 작은 숫자를 구하는 문제.
• 탐색은 현재 위치로 부터 바로 아래, 대각선으로 왼쪽/오른쪽 아래에 있는 칸으로 이동하여 이루어진다.

• 두번째 행 부터 각 열의 항목을 탐색하며 경로의 숫자 합을 구한다.
• 현재 칸 (i, j)에 도달할 수 있는 위치는 바로 위 (i-1, j), 왼쪽 대각선 위 (i-1, j-1), 오른쪽 대각선 위 (i-1, j+1)에 해당된다.
• 따라서 현재 칸의 값 matrix[i][j] 과 이전 위치의 값 matrix[i-1][k] (k = j-1 ~ j+1) 을 더한 값 중 최소값을 현재 칸의 값 matrix[i][j]으로 한다.

• 마지막 행의 값 중 최소 값을 결과 값으로 한다.

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 curr = matrix[i][j];
               matrix[i][j] = Integer.MAX_VALUE;
               for (int k = Math.max(j - 1, 0); k <= Math.min(j + 1, N - 1); ++k) {
                    matrix[i][j] = Math.min(matrix[i][j], curr + matrix[i - 1][k]);
                }
            }
        }
        
        int result = matrix[N - 1][0];
        for (int i = 1; i < N; ++i) {
            result = Math.min(result, matrix[N - 1][i]);
        }
        return result;
    }
}