[LeetCode] 931. Minimum Falling Path Sum

https://leetcode.com/problems/minimum-falling-path-sum/description/?envType=daily-question&envId=2024-01-19

LeetCode - The World's Leading Online Programming Learning Platform

LeetCode - Minimum Falling Path Sum

문제 유형 : 다이나믹 프로그래밍

문제 난이도 : Medium

 

문제

Given an n x n array of integers matrix, return the minimum sum of any falling path through matrix.

A falling path starts at any element in the first row and chooses the element in the next row that is either directly below or diagonally left/right. Specifically, the next element from position (row, col) will be (row + 1, col - 1), (row + 1, col), or (row + 1, col + 1).

 

n * n의 크기의 정수 배열 matrix가 주어진다. falling path로 내려오는 길의 최소 비용을 구하여라.

 

falling path는 0번째 행에서 시작해서 n-1번째 행까지 대각선으로 한 칸 내려오거나 바로 내려오는 것을 말합니다.

(row, col)에서 (row+1, col-1), (row+1, col) 또는 (row+1, col+1)로 이동할 수 있다는 뜻입니다.

 

 

풀이

dp배열을 n*n으로 만들고, 1e9의 크기로 만든다.

0번째 행은 matrix의 0번째 행과 똑같이 한다. base case이기 때문이다.

1번째 행부터 n-1번째 행까지는 dp[i-1]번째 행에서부터 채워준다.

dp[i+1][j+k] = min(dp[i+1][j+k], dp[i][j] + matrix[i+1][j+k]) (단, k는 -1 ~ 1)로 점화식을 세울 수 있다.

dp의 n-1번째 행에서 가장 작은 값을 반환하면 된다.

 

 

코드

C++

static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        const int n = matrix.size();
        vector<vector<int>> dp(n, vector<int>(n, 1e9));

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

        for(int i = 0; i < n-1; i++) {
            for(int j = 0; j < n; j++) {
                for(int k = -1; k < 2; k++) {
                    if(j+k < 0 || j+k >= n) continue;
                    dp[i+1][j+k] = min(dp[i+1][j+k], dp[i][j] + matrix[i+1][j+k]);
                }
            }
        }

        return *min_element(dp[n-1].begin(), dp[n-1].end());
    }
};