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

class Solution {
public:
    long long  rohit(int i,int j,int m,int n,vector<vector<int>> grid,vector<vector<long long>> &dp)
    {
        // if(i==m-1 && j==n-1)
        //  return grid[i][j];

        // if(i==m || j==n)
        //  return INT_MAX;

        // if(dp[i][j]!=-1)
        //  return dp[i][j];

        // long long a=rohit(i,j+1,m,n,grid,dp)+grid[i][j];
        // long long b=rohit(i+1,j,m,n,grid,dp)+grid[i][j];

        // return dp[i][j]=min(a,b);  

        dp[m-1][n-1]=grid[m-1][n-1];
        for(i=m-1;i>=0;i--)
        {
            for(j=n-1;j>=0;j--)
            {
                if(i==m-1 && j==n-1)
                 dp[i][j]=grid[m-1][n-1];

                else
                {
                    long long a=INT_MAX;
                    long long b=INT_MAX;
                    if(j<n-1)
                    a=dp[i][j+1]+grid[i][j];
                    if(i<m-1)
                    b=dp[i+1][j]+grid[i][j];
                    dp[i][j]=min(a,b);
                    //cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
                } 
            }
        } 
        return dp[0][0];
    }
    int minPathSum(vector<vector<int>>& grid) {
       int m=grid.size();
       int n=grid[0].size();
       vector<vector<long long>> dp(m,vector<long long> (n,-1));
       return rohit(0,0,m,n,grid,dp); 

    }
};
13600