these two function calls seem same to me but they gives different outputs.
I tried a lot to understand the problem. but i failed.
Can anybody help please.
code:
sum1==row wise cumulative sum for each column
sum2==column wise cumulative sum for each row
here the fun(n-1,m-1) function call gives correct output.
int fun(int r,int c){
int t1=0,t2=0;
if(r==n-1&&c==m-1)return max(sum1[r][c],sum2[r][c]);
if(r==n||c==m)return 0;
int &ret=dp[r][c];
if(ret!=-1)return ret;
t1=fun(r+1,c)+sum1[r][c];
t2=fun(r,c+1)+sum2[r][c];
return ret=max(t1,t2);
}
fun(0,0);//this gives wrong output
int fun(int r,int c){
int t1=0,t2=0;
if(r==0&&c==0)return max(sum1[r][c],sum2[r][c]);
if(r<0||c<0)return 0;
int &ret=dp[r][c];
if(ret!=-1)return ret;
t1=fun(r-1,c)+sum1[r][c];
t2=fun(r,c-1)+sum2[r][c];
return ret=max(t1,t2);
}
fun(n-1,m-1);//this gives correct output
As far as I can see, unknown important factors are the values of dp[][], sum1[][], sum2[][] arrays. Both given fun() implementations tend to do the same thing, but the second one is something like the "mirrored" version of the first one. In order to suffice the idea of doing the same thing, but with "mirrored" indexes, all three of the arrays for the second implementation should look like the "mirrored" versions of the corresponding arrays from the first implementation (e.g. sum1[i][j] == sum1[n — 1 — i][m — 1 — j] and etc.).
So I suppose, if I'm not mistaken, that the problem might be with the values of these arrays.