[LeetCode] 1289. Minimum Falling Path Sum II

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

Leetcode - Minimum Falling Path Sum II

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

문제 난이도 : Hard

 

문제

Given an n x n integer matrix grid, return the minimum sum of a falling path with non-zero shifts.

A falling path with non-zero shifts is a choice of exactly one element from each row of grid such that no two elements chosen in adjacent rows are in the same column.

 

n x n의 정수 행렬 grid가 주어진다.

falling path with non-zero shifts의 최소합을 구하시오.

각 행에서 하나의 요소를 고르는데, 인접한 행끼리는 같은 열의 요소를 고르지 않는 것을 말합니다.

 

풀이

dp[row][col] = grid[row][col]을 포함한 최소 0인덱스부터 row-1인덱스까지 하나씩 고른 합을 의미한다.

반복문을 3중첩 시켜서 단순히 O(n^3)의 문제로 풀수 있지만,

행을 한 번 돌때, 가장 작은 값의 인덱스와 두 번째로 작은 값의 인덱스를 저장시켜놓으면, O(n^2)의 시간으로 해결가능하다.

 

코드

C++

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& grid) {
        int n = grid.size();
        int m1 = 1e9;
        int m2 = 1e9;
        int idx1 = 0, idx2;
        vector<vector<int>> dp(n, vector<int>(n, 0));
        
        for(int i = 0; i < n; i++) {
            dp[0][i] = grid[0][i];
            if(dp[0][i] < m1) {
                idx2 = idx1;
                idx1 = i;
                m2 = m1;
                m1 = dp[0][i];
            } else if(dp[0][i] <= m2) {
                idx2 = i;
                m2 = dp[0][i];
            }
            // cout << dp[0][i] << " ";
        }
        // cout << idx1 << "|" << idx2 << "\n";

        for(int i = 1; i < n; i++) {
            int nextidx1 = 0, nextidx2;
            m1 = 1e9;
            m2 = 1e9;

            for(int j = 0; j < n; j++) {
                if(j == idx1) {
                    dp[i][j] = dp[i-1][idx2] + grid[i][j];
                } else {
                    dp[i][j] = dp[i-1][idx1] + grid[i][j];
                }

                if(dp[i][j] < m1) {
                    nextidx2 = nextidx1;
                    nextidx1 = j;
                    m2 = m1;
                    m1 = dp[i][j];
                } else if(dp[i][j] <= m2) {
                    nextidx2 = j;
                    m2 = dp[i][j];
                }
                // cout << dp[i][j] << " ";
            }

            idx2 = nextidx2;
            idx1 = nextidx1;
            // cout << idx1 << "|" << idx2 << "\n";
        }

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