# c++DP recursive and iteration

• ``````class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
vector<vector<int>> cache(grid.size(),vector<int>(grid[0].size(),-1));
cache[0][0] = grid[0][0];
for (int i = 1; i < grid.size(); i++)
cache[i][0] = cache[i - 1][0] + grid[i][0];
for (int j = 1; j < grid[0].size(); j++)
cache[0][j] = cache[0][j - 1] + grid[0][j];
return minPathSum(grid,cache,grid.size()-1,grid[0].size()-1);
}
int minPathSum(vector<vector<int>>& grid,
vector<vector<int>>& cache,int i, int j) {
if(cache[i][j] >= 0)
return cache[i][j];
return cache[i][j] = std::min(minPathSum(grid,cache,i-1,j), minPathSum(grid,cache,i,j-1))+grid[i][j];
}
};
``````

``````class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
vector<vector<int>> cache(grid.size(), vector<int>(grid[0].size(),0));
cache[0][0] = grid[0][0];
for(int i = 1; i < grid.size();i++) {//first colum
cache[i][0] += cache[i-1][0] + grid[i][0];
}
for(int j = 1; j < grid[0].size(); j++) {//first row
cache[0][j] += cache[0][j-1] + grid[0][j];
}
for(int i = 1; i < grid.size(); i++) {
for(int j = 1; j < grid[0].size();j++) {
cache[i][j] = min(cache[i-1][j],cache[i][j-1] ) + grid[i][j];
}
}
return cache[grid.size()-1][grid[0].size()-1];
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.