Simple solution using constant extra space


#1

//solution using constant space , no need of o(n) space also . simple solution
if(A.size()==0)
return 0;

int n=A.size();
if(n==1)
return A[0][0];

for(int i=n-1;i>0;--i)
{
    int l=i-1;
    for(int j=A[l].size()-1;j>=0;--j)
    {
        A[i-1][j]+=min(A[i][j],A[i][j+1]); // we just add up the min of two values to the one above it
    }
}

return A[0][0];