longest common subsequence codeforces code example

Example 1: longest common subsequence

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        """
        text1: horizontally
        text2: vertically
        """
        dp = [[0 for _ in range(len(text1)+1)] for _ in range(len(text2)+1)]
        
        for row in range(1, len(text2)+1):
            for col in range(1, len(text1)+1):
                if text2[row-1]==text1[col-1]:
                    dp[row][col] = 1+ dp[row-1][col-1]
                else:
                    dp[row][col] = max(dp[row-1][col], dp[row][col-1])
        return dp[len(text2)][len(text1)]

Example 2: 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;
}