Help in a Leetcode DP Problem

general
1

Hello Everyone,

The question is
- LeetCode
I want to know the recursion code for this problem so that I can formulate it into DP.

Here is my code

int f(vector& A, int i, int len1, vector& B, int j, int len2)
{
if(i==len1 or j==len2) return 0;

   if(A[i]==B[j]) return 1 + f(A,i+1,len1,B,j+1,len2);
    
    else return  max( f(A,i,len1,B,j+1,len2), f(A,i+1,len1,B,j,len2) ); 

}

The problem lies in the else part of the code but somehow I am not able to visualise how to correct it due to recursive calls.

Also since the problem is same as Longest Common Substring.
how is this code working fine.

public static int LCSubStrM1(char[] X, char[] Y, int m, int n, int lcsCount) {
if (m <= 0 || n <= 0)
return lcsCount;

	int lcsCount1=lcsCount;
	if (X[m - 1] == Y[n - 1])
		lcsCount1 = LCSubStrM1(X, Y, m - 1, n - 1, lcsCount + 1);

	int lcsCount2 = LCSubStrM1(X, Y, m, n - 1, 0);
	int lcsCount3 = LCSubStrM1(X, Y, m - 1, n, 0);

	return Math.max(lcsCount1, Math.max(lcsCount2, lcsCount3));
}

This is my first post here. @vijju123 @anon55659401 @l_returns please help.

2

Here’s how I did it :
(k is 1 if last element at i-1,j-1 was selected, else it is 0)

int f(int i,int j,int k,vector<int> &A,vector<int> &B){
        if(i==A.size() || j==B.size())return 0;
        int &ans=dp[i][j][k];
        if(ans!=-1)return ans;
        int a=-1,b=-1,c=-1;
        
        if(k){
            
            if(A[i]==B[j]){
                a=1+f(i+1,j+1,1,A,B);
            }else{
                a=b=c=0;
            }
            
        }else{
            
            if(A[i]==B[j]){
                a=1+f(i+1,j+1,1,A,B);
            }
            b=f(i,j+1,0,A,B);
            c=f(i+1,j,0,A,B);
        }
        
        return ans=max({a,b,c});
    }
3

Thanks for the code but I want some advice for debugging my code so that it would get accepted. I just want to know where am I going wrong.