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


# Sol 3: 
# C.T. 

# if you also want to print the path along with the sum of all numbers along the path. 
'''
# Example usage
solution = Solution()
grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]
min_sum, path = solution.minPathSum(grid)
print(f"Minimum Path Sum: {min_sum}")
print(f"Path: {path}")

Minimum Path Sum: 7
Path: [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)]


How the Backtracking Works:
Path Construction (Forward Pass):

During the forward pass (when we construct the dp table and the path table), we store information about where we came from at each step. For example, if we're filling cell (i, j), we store whether we arrived there from the left or from above:
If we came from above, we store (i-1, j).
If we came from the left, we store (i, j-1).
Backtracking (Reverse Pass):

Starting at the bottom-right corner (m-1, n-1), we consult the path table to find where we came from. The path table stores the coordinates of the previous cell, so we can move "backward" by following these references.
At each iteration of the loop, we update r and c using the values stored in path[r][c], which are the coordinates of the previous cell. This is how the while loop moves backward.




'''

from typing import List, Tuple

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> Tuple[int, List[Tuple[int, int]]]:
        m, n = len(grid), len(grid[0])
        
        # Initialize dp and path tracking arrays
        dp = [[0] * n for _ in range(m)]
        path = [[(None,None)] * n for _ in range(m)]
        
        # Base case: start at the top-left corner
        dp[0][0] = grid[0][0]
        
        # Fill the first row (can only come from the left)
        for j in range(1, n):
            dp[0][j] = dp[0][j-1] + grid[0][j]
            path[0][j] = (0, j-1)  # Track the previous cell (from the left)
        
        # Fill the first column (can only come from above)
        for i in range(1, m):
            dp[i][0] = dp[i-1][0] + grid[i][0]
            path[i][0] = (i-1, 0)  # Track the previous cell (from above)
        
        # Fill the rest of the dp array
        for i in range(1, m):
            for j in range(1, n):
                if dp[i-1][j] < dp[i][j-1]:
                    dp[i][j] = dp[i-1][j] + grid[i][j]
                    path[i][j] = (i-1, j)  # Came from above
                else:
                    dp[i][j] = dp[i][j-1] + grid[i][j]
                    path[i][j] = (i, j-1)  # Came from the left
        
        # print(path)
        # Now backtrack to find the path from bottom-right to top-left
        path_taken = []
        r, c = m - 1, n - 1
        while r is not None and c is not None:
            path_taken.append((r, c))
            # print(path_taken)
            r, c = path[r][c]
        
        # Since we backtrack, reverse the path to get the correct order
        path_taken.reverse()
        print(path_taken)
        # The minimum path sum is at dp[m-1][n-1]
        return dp[m-1][n-1]

"""
# Sol 2: O(m*n) time and space 
# C. T. 
class Solution:
    def minPathSum(self, grid: List[List[int]]) -> Tuple[int, List[Tuple[int, int]]]:
        m, n = len(grid), len(grid[0])
        
        # Initialize dp and path tracking arrays
        dp = [[0] * n for _ in range(m)]
        
        # Base case: start at the top-left corner
        dp[0][0] = grid[0][0]
        
        # Fill the first row (can only come from the left)
        for j in range(1, n):
            dp[0][j] = dp[0][j-1] + grid[0][j]
        
        # Fill the first column (can only come from above)
        for i in range(1, m):
            dp[i][0] = dp[i-1][0] + grid[i][0]
        
        # Fill the rest of the dp array
        for i in range(1, m):
            for j in range(1, n):
                if dp[i-1][j] < dp[i][j-1]:
                    dp[i][j] = dp[i-1][j] + grid[i][j] # Came from above
                else:
                    dp[i][j] = dp[i][j-1] + grid[i][j] # Came from the left

        return dp[m-1][n-1]
"""

"""
# Solution 1: O(m*n) time and space complexity
# https://www.youtube.com/watch?v=ItjZdu6jEMs
# https://leetcode.com/problems/minimum-path-sum/discuss/793480/python-DP-with-explanation
class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        r = len(grid)
        c = len(grid[0])
        
        dp = [[0]*c for _ in range(r)]
        
        for i in range(r):
            for j in range(c):
                if i == 0 and j == 0:
                    dp[i][j] = grid[i][j]
                elif i == 0 and j > 0:
                    dp[i][j] = grid[i][j] + dp[i][j-1]
                elif i > 0 and j==0:
                    dp[i][j] = grid[i][j] + dp[i-1][j]
                else:
                    left = dp[i][j-1]
                    upper = dp[i-1][j]
                    # print(dp)
                    dp[i][j] = min(left,upper) + grid[i][j]
        
        # print(dp)
        return dp[r-1][c-1]
"""       
21300