CF 683 Div2 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;
    return dp[i][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


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)
        else if(a[i-1]==b[j-1])

I tried this in tabulation approach.

I am not getting what should I change in the recursive approach?

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

Thanks I got it now

1 Like

Here does descent order mean in decreasing order?

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


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