Hard

Minimum Falling Path Sum II

LAB

Return the minimum falling path sum choosing one value per row with no two adjacent rows using the same column.

EXAMPLES

Example 1

Input
{
  "grid": [
    [
      1,
      2,
      3
    ],
    [
      4,
      5,
      6
    ],
    [
      7,
      8,
      9
    ]
  ]
}

Output
13

FUNCTION SHAPE

grid: intMatrix→int

SOLUTION NOTE

Identical to Paint House II. Use prefix/suffix min for O(k) per row instead of O(k²).

Reveal reference solution +

pythonREFERENCE

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

    @cache
    def prefix_min(i, c):
        if c < 0: return float('inf')
        return min(prefix_min(i, c - 1), dp(i, c))

    @cache
    def suffix_min(i, c):
        if c >= k: return float('inf')
        return min(dp(i, c), suffix_min(i, c + 1))

    @cache
    def dp(i, c):
        if i == n - 1: return grid[i][c]
        return grid[i][c] + min(prefix_min(i + 1, c - 1), suffix_min(i + 1, c + 1))

    return min(dp(0, c) for c in range(k))

TimeO(n × k)

SpaceO(n × k)

Open on LeetCode ↗