CF 683 Div2 Problem D

help
#1

https://codeforces.com/contest/1447/problem/D

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

#2

Anyone?

#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
#4 
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?

#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
#6

Thanks I got it now

1 Like
#7

Here does descent order mean in decreasing order?

If yes then does it matter what we do inc or dec ?

#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