Minimum Path Sum

//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;
}