Minimum Path Sum

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.

class Solution {

public:

int minPathSum(vector<vector<int> > &grid) {

    int m = grid.size();

    

    if(m <= 0)

        return  0;

    

    int n = grid[0].size();

    vector< vector<int> > v;

    

    for(int i =0; i < m; i++)

    {

        vector<int> vj;

        for(int j = 0; j < n; j++)

        {

            vj.push_back(0);

        }

        v.push_back(vj);

    }

    

    v[0][0] = grid[0][0];

    

    for(int i  = 1  ; i < m; i++)

    {

        v[i][0] = grid[i][0] + v[i-1][0];    

    }

    for(int j = 1  ; j < n; j++)

    {

        v[0][j] = grid[0][j] + v[0][j-1];    

    }

    

    for(int i = 1; i < m; i++)

    {

        for(int j  = 1; j < n; j++)

        {

            v[i][j] =  grid[i][j] + min(v[i-1][j], v[i][j-1]);       

        }

    }

    

    return v[m-1][n-1];

}

};