1289. Minimum Falling Path Sum II

[zeikar]

Problem link

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

Problem Summary

행끼리 인접하지 않은 열의 수를 더해서 최소가 되도록 맨 아래까지 가는 합을 구하는 문제.

Solution

O(n^3) 풀이는 매우 쉬운 DP. O(n^2) 풀이를 생각해보자.
그리디하게 생각해보면 된다.

다음 row로 넘어갈 때 col이 같지만 않으면 된다. 즉, col이 어떤 곳이라도 찍을 수 있다는 것. 이를 잘 이용하면 전체 스캔할 필요 없이 최솟값인 곳과 두번째 최솟값인 곳만을 탐색할 수 있다.

문제의 1번 예시를 보면 두번째 row에서 답이 될 수 있는 첫번째 row의 값은 1과 2밖에 없다. 3을 찍을 경우 1, 2를 찍었을 때보다 전체 합이 커지게 된다.

즉 모든 row를 탐색할 필요 없이 이전 까지의 합의 최솟값과 두번째 최솟값인 값들만 탐색해주면 된다. -> O(n^2)

Source Code

O(n^3)

class Solution:
    def minFallingPathSum(self, grid: List[List[int]]) -> int:
        n = len(grid)

        @cache
        def solve(row, col):
            if row == n:
                return 0
            
            ans = 987654321
            for j in range(n):
                if j == col:
                    continue
                
                ans = min(ans, solve(row + 1, j) + grid[row][j])
            
            return ans

        return solve(0, -1)

O(n^2)

class Solution:
    def minFallingPathSum(self, grid: List[List[int]]) -> int:
        n = len(grid)
        dp = [[987654321] * n for i in range(n)]
        dp[0] = grid[0]
        print(dp)

        for i in range(1, n):
            min1, min2 = 0, 0
            min1v, min2v = 987654321, 987654321
            for j in range(n):
                if dp[i - 1][j] <= min1v:
                    min2 = min1
                    min2v = min1v
                    min1 = j
                    min1v = dp[i - 1][j]
                elif dp[i - 1][j] <= min2v:
                    min2 = j
                    min2v = dp[i - 1][j]
            
            print(min1, min2)
            for j in range(n):
                if j != min1:
                    dp[i][j] = min(dp[i][j], dp[i - 1][min1] + grid[i][j])
                if j != min2:
                    dp[i][j] = min(dp[i][j], dp[i - 1][min2] + grid[i][j])
        
        print(dp)
        return min(dp[-1])