931. Minimum Falling Path Sum

문제

https://leetcode.com/problems/minimum-falling-path-sum/description/

풀이

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;

        int[][] dp = new int[n][n];

        for(int i = 0; i < n; i++) {
            dp[0][i] = matrix[0][i];
        }

        for(int i = 1; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(j + 1 < n && j - 1 >= 0) {
                  dp[i][j] = Math.min(dp[i-1][j+1],Math.min(dp[i-1][j-1], dp[i-1][j])) + matrix[i][j];
                } else if(j + 1 < n ) {
                    dp[i][j] = Math.min(dp[i-1][j+1], dp[i-1][j]) + matrix[i][j];
                } else {
                    dp[i][j] = Math.min(dp[i-1][j], dp[i-1][j-1]) + matrix[i][j];
                }
            }
        }

        int answer = Integer.MAX_VALUE;
        for(int i = 0; i < n; i++) {
            answer = Math.min(answer, dp[n-1][i]); 
        }

        return answer;
    }
}

• 경우의 수가 총 세가지가 존재
  • j-1, j, j+1에서 올 수 있는 경우 (j + 1 < n && j - 1 >= 0)
  • j-1, j에서 올 수 있는 경우 (오른쪽 끝, j == n -1)
  • j, j+1에서 올 수 있는 경우 (왼쪽 끝, j == 0)