<p>Given an <code>n x n</code> array of integers <code>matrix</code>, return <em>the <strong>minimum sum</strong> of any <strong>falling path</strong> through</em> <code>matrix</code>.</p>

<p>A <strong>falling path</strong> 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 <code>(row, col)</code> will be <code>(row + 1, col - 1)</code>, <code>(row + 1, col)</code>, or <code>(row + 1, col + 1)</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/11/03/failing1-grid.jpg" style="width: 499px; height: 500px;" />
<pre>
<strong>Input:</strong> matrix = [[2,1,3],[6,5,4],[7,8,9]]
<strong>Output:</strong> 13
<strong>Explanation:</strong> There are two falling paths with a minimum sum as shown.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/11/03/failing2-grid.jpg" style="width: 164px; height: 365px;" />
<pre>
<strong>Input:</strong> matrix = [[-19,57],[-40,-5]]
<strong>Output:</strong> -59
<strong>Explanation:</strong> The falling path with a minimum sum is shown.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == matrix.length == matrix[i].length</code></li>
	<li><code>1 &lt;= n &lt;= 100</code></li>
	<li><code>-100 &lt;= matrix[i][j] &lt;= 100</code></li>
</ul>

class Solution:
    def minFallingPathSum(self, matrix: list[list[int]]) -> int:
        n = len(matrix)
        ans1 = ans2 = ans3 = sys.maxsize
        for i in range(n):
            # falling_path  = self.simpleRecursion(matrix, 0, i)
            # ans1 = min(ans1, falling_path)
            dp = [[None] * n for i in range(n)]
            falling_path = self.bottomUp(matrix, 0, i, dp)
            ans2 = min(ans2, falling_path)

        ans3 = self.topDown(matrix, n)
        return ans3

    def simpleRecursion(self, matrix, row, col):
        if row == len(matrix) - 1 and 0 <= col < len(matrix):
            return matrix[row][col]
        if col < 0 or col >= len(matrix):
            return sys.maxsize

        down = matrix[row][col] + self.simpleRecursion(matrix, row + 1, col)
        leftDiagonal = matrix[row][col] + self.simpleRecursion(matrix, row + 1, col - 1)
        rightDiagonal = matrix[row][col] + self.simpleRecursion(matrix, row + 1, col + 1)

        return min(down, leftDiagonal, rightDiagonal)

    def bottomUp(self, matrix, row, col, dp):
        if row == len(matrix) - 1 and 0 <= col < len(matrix):
            return matrix[row][col]
        if col < 0 or col >= len(matrix):
            return sys.maxsize
        if dp[row][col] is not None:
            return dp[row][col]

        down = matrix[row][col] + self.bottomUp(matrix, row + 1, col, dp)
        leftDiagonal = matrix[row][col] + self.bottomUp(matrix, row + 1, col - 1, dp)
        rightDiagonal = matrix[row][col] + self.bottomUp(matrix, row + 1, col + 1, dp)

        dp[row][col] = min(down, leftDiagonal, rightDiagonal)
        return dp[row][col]

    def topDown(self, matrix, n):
        dp = [[0] * n for _ in range(n)]
        for i in range(n):
            dp[n - 1][i] = matrix[n-1][i]

        for i in range(n - 2, -1, -1):
            for j in range(n):
                down = matrix[i][j] + dp[i + 1][j]
                leftDiagonal = sys.maxsize if j - 1 < 0 else matrix[i][j] + dp[i + 1][j-1]
                rightDiagonal = sys.maxsize if j + 1 >= n else matrix[i][j] + dp[i + 1][j + 1]
                dp[i][j] = min(down, leftDiagonal, rightDiagonal)

        falling_path = sys.maxsize
        for i in range(n):
            falling_path = min(falling_path, dp[0][i])

        return falling_path


        
17700