Longest Common Subsequence ( LCS )

Resources:

ডাইনামিক প্রোগ্রামিং: লংগেস্ট কমন সাবসিকোয়েন্স

GeekGeeks 

Practice Dynamic Programming! Educational DP Contest: F - LCS 

Tushar Roy Video

DP: Find elements of LCS ( Hackerrank Problem )  

Code:

	#include<bits/stdc++.h>
	using namespace std;
	const int maxn = 1005;
	int dp[maxn][maxn];
	string A,B,ans;
	int LCS(int i, int j)
	{
	if(A[i] == '\0' || B[j] == '\0') return 0;
	else if (dp[i][j] != -1) return dp[i][j];
	int len1 = 0, len2 = 0, mx = 0;
	if(A[i] == B[j])
	len1 = 1 + LCS(i+1, j+1);
	else{
	len1 = LCS(i+1, j);
	len2 = LCS(i, j+1);
	}
	return dp[i][j] = max(len1, len2);
	}
	void printLCS(int i, int j)
	{
	if(A[i] == '\0' || B[j] == '\0'){
	cout << ans << endl;
	return;
	}
	if(A[i] == B[j]){
	ans += A[i];
	printLCS(i+1, j+1);
	}
	else{
	if(dp[i+1][j] > dp[i][j+1])
	printLCS(i+1, j);
	else
	printLCS(i, j+1);
	}
	}
	int main()
	{
	memset(dp, -1, sizeof dp);
	cin >> A >> B;
	cout << LCS(0,0)<<endl;
	ans = "";
	printLCS(0,0);
	return 0;
	}

view raw LCS.cpp hosted with ❤ by GitHub

Problem list:

1013 - Love Calculator   SOLUTION

Share: