//64
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.
Note: You can only move either down or right at any point in time.
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int minPathSum(vector<vector<int> >& grid) {
// if(grid.size()==0){
// return 0;
// }
//init dp
vector<vector<int> > dp(grid.size(),vector<int>(grid[0].size()));
int m=grid.size();
int n=grid[0].size();
dp[0][0]=grid[0][0];
//int i=1,while m=1 won't enter loop;
//or two for(int i=0;i<m;i++) dp[i][0],for(int j=0;j<n)...
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(i>=1) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
if(j>=1) {
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
}
}
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j];
}
}
return dp[m-1][n-1];
}
};
int main(){
int m=1,n=4;
//int arr[m][n]={{1,2,6,9},{10,4,3,2},{1,7,5,3}};
int arr[m][n]={{9,1,4,8}};
vector<vector<int> > grid(m,vector<int>(n));
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
grid[i][j]=arr[i][j];
}
}
cout<<Solution().minPathSum(grid)<<endl;
return 0;
}
