Minimum Falling Path Sum

그래도 꽤 재밌어보이는 DP 문제를 풀었다. 확실히 DP로직을 Matrix 안에서 짜는거랑 그냥 썡으로 생각하는거랑 많이 차이가 나는거같고 이번에 풀었던 문제는 쉬운 편에 속하는 DP 문제였다. 첫번째 줄부터 시작해서 3가지 방향으로 뻗어가며 믿으로 갈 수 있는데 이 루트중에서 가장 최소의 합을 구하고 반환하면 되는 문제이다.

이 문제는 재귀 식으로도 풀 수 있다. 그런데 그렇게 되면은 결국 한칸씩 밑으로 갈때마다 3방향의 계산을 하면서 모든 가능성을 확인해야 하기 때문에 결국 TLE로 넘어간다. 그래서 이 문제는 이런 반복되는 작업을 하지말고 오로지 최소한의 합만을 각 줄에서 저장하면서 가면 되는 문제이다. 그렇기 때문에 변하지 않는 첫번째 줄을 넘어가고 두번째 줄부터 시작해서 조건에만 맞다면은 최소 값을 저장해주고 가장 마지막 줄에 있는 최소 값을 반환하는거로 쉽게 풀 수 있었다.

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