Simple c++ solution 80ms


  • 0
    R

    class Solution {
    public:
    int minPathSum(vector<vector<int> > &grid) {
    int M = grid.size();
    int N = grid[0].size();
    int i,j;
    if (M == 0 || N == 0)
    return 0;

        int **sum;
        sum = new int*[M];
        for(i=0;i<M;i++)
            sum[i] = new int[N];
        sum[0][0] = grid[0][0];
        for(i=1; i< M ; i++)
            sum[i][0] = sum[i-1][0] + grid[i][0];
        for(int j=1; j< N ; j++) 
            sum[0][j] = sum[0][j-1] + grid[0][j];
        
        for(i=1;i<M;i++) {
            for(j=1;j<N; j++) {
                sum[i][j] = grid[i][j] + min(sum[i-1][j], sum[i][j-1]);
            }
        }
        return sum[M-1][N-1];
       
        
    }
    

    };


Log in to reply
 

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