Can someone help in DP problem with memoization approach.
I tried this but this will not work for cases like a=“bab” and b=“bba”
int fun(int i, int j)
{
if(i==n || j==m)
return 0;
if(dp[i][j]!=-1)
return dp[i][j];
if(a[i]==b[j])
return dp[i][j]=2+fun(i+1,j+1);
return dp[i][j]=max({0, fun(i+1,j)-1, fun(i,j+1)-1});
}
@everule1 @carre
carre
November 17, 2020, 4:08pm
3
the problem has an editorial, what part you don’t understand? To give an alternative explanation it is easier to see what is missing/wrong in your logic? Can you develop your thoughts a bit?
1 Like
for(int i=0;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
if(i==0 || j==0)
dp[i][j]=0;
else if(a[i-1]==b[j-1])
dp[i][j]=2+dp[i-1][j-1];
else
dp[i][j]=max({0,dp[i][j-1]-1,dp[i-1][j]-1});
ans=max(ans,dp[i][j]);
}
}
I tried this in tabulation approach.
I am not getting what should I change in the recursive approach?
carre
November 17, 2020, 6:38pm
5
it’s not bad but you need to call that function for every (i,j) in descent order:
int ret=0;
for(int i=n-1;i>=0;--i){
for(int j=m-1;j>=0;--j){
ret = max(ret,fun(i,j));
}
}
cout << ret;
otherwise, if a[i]==b[j] you jump to (i+1,j+1) and you are not checking others (i+1,j) or (i,j+1)
1 Like
Here does descent order mean in decreasing order?
If yes then does it matter what we do inc or dec ?
carre
November 17, 2020, 6:59pm
8
yes
no, it’s not important, just that you need the larger indexes to get the lower ones so it was intuitive to me to calculate the larger ones first but it’s the same
1 Like