[LeetCode] 931. Minimum Falling Path Sum

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

Minimum Falling Path Sum - LeetCode

Minimum Falling Path Sum - Medium

 

Matrix가 주어졌을때, falling path를 따라갔을때 가장 최소값을 구하는 문제다.

falling path란, 가장 윗줄 부터 시작해 바로 아래나 양 옆 대각선아래로 가는 path이다.

path에 있는 matrix cost는 모두 더해야한다.

 

dp 문제이다.

path를 따랐을때, i,j 칸에서의 최소값을 dp[1][j]로 놓자.

이 칸에 도달하려면 바로 윗칸(dp[0][j])이나 왼쪽 윗칸(dp[0][j-1]) 또는 오른쪽 윗칸(dp[0][j+1])에서 와야한다.

그렇다면 dp[1][j] = min (dp[0][j], dp[0][j-1], dp[0][j+1]) + matrix[i][j] 가 된다.

바로 전칸의 정보만 있으면 되므로 dp는 2 x n 배열이면 충분하다.

마지막칸에서의 최소값을 구해주면 원하는 답이 된다.

 

전체 풀이 코드

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int dp[2][105],n=matrix.size(),m=INT_MAX;
        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++) {
                dp[1][j] = dp[0][j];
                if (j) dp[1][j] = min(dp[1][j],dp[0][j-1]);
                if (j<n-1) dp[1][j] = min(dp[1][j], dp[0][j+1]);
                dp[1][j] += matrix[i][j];
            }
            for (int j=0; j<n; j++) dp[0][j] = dp[1][j];
        }
        for (int i=0; i<n; i++) m = min(m,dp[0][i]);
        return m;
    }
};