Longest Common Subsequence (Dynamic Programming code example

Example 1: longest common subsequence codefroces

#include<bits/stdc++.h>
using namespace std;

const int MAX = 1001;

int dp[MAX][MAX];
bool visited[MAX][MAX];
int x, y;
string s1, s2;

int lcs(int i, int j)
{
    if(i == x || j == y)
        return 0;

    if(visited[i][j])
        return dp[i][j];

    visited[i][j] = true;
    int ans = 0;
    if(s1[i] == s2[j])
    {
        ans = max(ans, 1+lcs(i+1, j+1));
    }
    else
    {
        ans = max(ans, lcs(i+1, j));
        ans = max(ans, lcs(i, j+1));
    }

    dp[i][j] = ans;
    return ans;
}

int main()
{
    cin >> x >> y;
    cin >> s1 >> s2;

    for(int i=0; i<=x; i++)
    {
        for(int j=0; j<=y; j++)
        {
            visited[i][j] = false;
        }
    }

    cout << lcs(0, 0);
    return 0;
}

Example 2: longest common subsequence

int maxSubsequenceSubstring(char x[], char y[], 
                            int n, int m) 
{ 
    int dp[MAX][MAX]; 
  
    // Initialize the dp[][] to 0. 
    for (int i = 0; i <= m; i++) 
        for (int j = 0; j <= n; j++) 
            dp[i][j] = 0; 
  
    // Calculating value for each element. 
    for (int i = 1; i <= m; i++) { 
        for (int j = 1; j <= n; j++) { 
  
            // If alphabet of string X and Y are 
            // equal make dp[i][j] = 1 + dp[i-1][j-1] 
            if (x[j - 1] == y[i - 1]) 
                dp[i][j] = 1 + dp[i - 1][j - 1]; 
  
            // Else copy the previous value in the 
            // row i.e dp[i-1][j-1] 
            else
                dp[i][j] = dp[i][j - 1]; 
        } 
    } 
  
    // Finding the maximum length. 
    int ans = 0; 
    for (int i = 1; i <= m; i++) 
        ans = max(ans, dp[i][n]); 
  
    return ans; 
}