<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:
int f(int r,int c,vector<vector<int>>&a,vector<vector<int>>&dp){
        // if(r==0&&c==0)
        //     return dp[r][c]=a[0][0];
        // if(r<0||c<0)
        // return 1e9;
        // if(dp[r][c]!=-1)
        //  return dp[r][c];
        // int up=a[r][c]+f(r-1,c,a,dp);
        // int left=a[r][c]+f(r,c-1,a,dp);
        // return dp[r][c]=min(up,left);

        // for(int i=0;i<=r;i++){
        //     for(int j=0;j<=c;j++){
        //         int left=INT_MAX,up=INT_MAX;
        //         if(i==0&&j==0){
        //             dp[i][j]=a[i][j];
        //             continue;
        //         }
        //         if(i>=1)
        //         up=a[i][j]+dp[i-1][j];
        //         if(j>=1)
        //         left=a[i][j]+dp[i][j-1];
        //         dp[i][j]=min(left,up);
        //     }
        // }
        // return dp[r][c];

        vector<int>prev(c+1,0);
        for(int i=0;i<=r;i++){
            vector<int>temp(c+1,0);
            for(int j=0;j<=c;j++){
                int left=INT_MAX,up=INT_MAX;
                if(i==0&&j==0){
                    temp[0]=a[i][j];
                    continue;
                }
                if(i>=1)
                up=a[i][j]+prev[j];
                if(j>=1)
                left=a[i][j]+temp[j-1];
                temp[j]=min(left,up);
            }
            prev=temp;
        }
        return prev[c];
    }
    int minPathSum(vector<vector<int>>& grid) {
        vector<vector<int>>dp(grid.size(),vector<int>(grid[0].size(),-1));
        int sum=0;
        return f(grid.size()-1,grid[0].size()-1,grid,dp);
    }
};
13400