Help ! PLEASE ! what can i do better ( only 80/300 )


#1

vector<vector > t;
int rec(vector<vector > arr , int i,int j){
//if(t[i][j] != -1) return t[i][j];
if(i==0 && j == 0){
if(t[i][j] !=-1) return t[0][0];
//cout<<“1 = i,j = “<<i<<”,”<<j<<endl;
return t[i][j] = arr[0][0];
}
else if(i==0){
if(t[i][j-1] != -1) return t[i][j] = arr[i][j] + t[i][j-1];
return t[i][j] = arr[i][j] + rec(arr,i,j-1 );
}
else if(j==0){
if(t[i-1][j] != -1) return t[i][j] = arr[i][j] + t[i-1][j];
return t[i][j] = arr[i][j] + rec(arr,i-1,j );
}
else {
int left = t[i-1][j];
int right = t[i][j-1];
if(left != -1 && right != -1){
return t[i][j] = min(arr[i][j] + left ,arr[i][j] + right );
}
else if(left != -1){
return t[i][j] = min(arr[i][j] + left ,arr[i][j] + rec(arr,i,j-1 ) );
}
else if(right != -1){
return t[i][j] = min(arr[i][j] + rec(arr,i-1,j ) ,arr[i][j] + right );
}
else
return t[i][j] = min(arr[i][j] + rec(arr,i-1,j ) ,arr[i][j] + rec(arr,i,j-1 ) );
}
}

int Solution::minPathSum(vector<vector > &A) {
t = A;
for(int i=0;i<A.size();i++){
for(int j = 0;j<A[0].size();j++){
t[i][j] = -1;
}
}
int ans = rec(A,A.size()-1,A[0].size()-1);
return ans;
}


#2

hey i think you implemented brute force approach
this is a dp problem
follow my solution , i had written comments for you.
this will help you to solve next problem too.
Still having doubt , revert back.

int Solution::minPathSum(vector<vector > &A) {
int n=A.size();
int m=A[0].size();
int i,j;
int dp[n][m];
dp[n-1][m-1]=A[n-1][m-1];//initializing base condition
for(i=m-2;i>=0;i–)
dp[n-1][i]=A[n-1][i]+dp[n-1][i+1];//initializing base condition as there is only one way to move from here
for(i=n-2;i>=0;i–)
dp[i][m-1]=A[i][m-1]+dp[i+1][m-1];//initializing base condition
for(i=n-2;i>=0;i–)
for(j=m-2;j>=0;j–)
dp[i][j]=A[i][j]+min(dp[i+1][j],dp[i][j+1]);//then bottom up approach dp

return dp[0][0];

}