<p>Given a <code>m x n</code> <code>grid</code> filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.</p>

<p><strong>Note:</strong> You can only move either down or right at any point in time.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/11/05/minpath.jpg" style="width: 242px; height: 242px;" />
<pre>
<strong>Input:</strong> grid = [[1,3,1],[1,5,1],[4,2,1]]
<strong>Output:</strong> 7
<strong>Explanation:</strong> Because the path 1 &rarr; 3 &rarr; 1 &rarr; 1 &rarr; 1 minimizes the sum.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> grid = [[1,2,3],[4,5,6]]
<strong>Output:</strong> 12
</pre>

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

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 200</code></li>
	<li><code>0 &lt;= grid[i][j] &lt;= 200</code></li>
</ul>

'''
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.
- m rows
- n columns
- non-negative numbers (includes 0's)


Note: You can only move either down or right at any point in time.
- this tells us the minimum path sum for the bottom row and rightmost column

7   6   3
8   7   2
7   3   1

'''

from functools import reduce

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        
        m = len(grid) # no. of rows
        n = len(grid[0]) # no. of columns

        if m == 1 and n == 1:
            return grid[0][0]

        if m == 1 or n == 1:
            if m == 1:
                return reduce(lambda x, y: x+y, grid[0]) # sum of lone row
            if n == 1:
                col_sum = 0
                for r in range(m):
                    col_sum += grid[r][0]   # sum of lone col
                return col_sum
                
        dp = [[0 for _ in range(n)] for _ in range(m)]
        
        
        # fill last row
        sum = 0
        for j in range(n-1, -1, -1):
            dp[m-1][j] = sum + grid[m-1][j]
            sum = dp[m-1][j]
        
        # fill last col
        sum = 0
        for i in range(m-1, -1, -1):
            dp[i][j-1] = sum + grid[i][j-1]
            sum = dp[i][j-1]

        print(dp)


        for j in range(n-2, -1, -1):
            for i in range(m-2, -1, -1):
                dp[i][j] = grid[i][j] + min(dp[i+1][j], dp[i][j+1])
        
        print(dp)

        return dp[0][0]



19600