931. Minimum Falling Path Sum

문제)

931. Minimum Falling Path Sum

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).

 

Example 1:

Input: matrix = [[2,1,3],[6,5,4],[7,8,9]]
Output: 13
Explanation: There are two falling paths with a minimum sum as shown.

Example 2:

Input: matrix = [[-19,57],[-40,-5]]
Output: -59
Explanation: The falling path with a minimum sum is shown.

 

Constraints:

• n == matrix.length == matrix[i].length
• 1 <= n <= 100
• -100 <= matrix[i][j] <= 100

 

문제 이해)

- 0 row에서 부터 시작해서 element를 선택해서 다음 row로 이동새 col은 col-1, col, col+1을 선택할 있다. 최종 row까지 도달 시 mimum sum은 무엇인가?

- 문제를 단순화하면 0번째 row에서 n-1번째까지 이동하는데 가장 짧은 거리는?

- 테이블을 하나 생성해서 현재 기준으로 가장 최소 path를 저장해간다면 O(n)에 문제 풀이가 가능

 

솔루션1)

class Solution:
    def minFallingPathSum(self, matrix):
        n = len(matrix)
        dp = [[0] * n for i in range(n)]

        for r in range(n):
            for c in range(n):
                if r == 0:
                    dp[r][c] = matrix[r][c]
                elif c == 0:
                    # first column
                    dp[r][c] = matrix[r][c] + min(dp[r-1][c], dp[r-1][c+1])
                elif c == (n-1):
                    # last column
                    dp[r][c] = matrix[r][c] + min(dp[r-1][c-1], dp[r-1][c])
                else:
                    dp[r][c] = matrix[r][c] + min(dp[r - 1][c - 1], dp[r - 1][c], dp[r - 1][c+1])

        return min(dp[-1])

솔루션2)

솔루션1에서 dp 테이블을 만들지 않고 더 간결화한 코드

class Solution:
    def minFallingPathSum(self, matrix):
        n = len(matrix)
        for r in range(1, n):
            for c in range(n):
                if c == 0:
                    # first column
                    matrix[r][c] = matrix[r][c] + min(matrix[r-1][c], matrix[r-1][c+1])
                elif c == (n-1):
                    # last column
                    matrix[r][c] = matrix[r][c] + min(matrix[r-1][c-1], matrix[r-1][c])
                else:
                    matrix[r][c] = matrix[r][c] + min(matrix[r - 1][c - 1], matrix[r - 1][c], matrix[r - 1][c+1])

        return min(matrix[-1])