Problem 11: Longest Common Subsequence
Problem Statement: Given two strings, compute the length of their longest common subsequence using dynamic programming.
Input
Two lines each containing a string.
Output
Print the length of the longest common subsequence.
Examples
Input:
AGGTAB
GXTXAYB
Output:
4
Solution Explanation
Method 1: Build a DP table where dp[i][j] represents the LCS length of the first i and first j characters; use recurrence comparing characters. Method 2: Use recursion with memoization to solve the problem top-down, although it is less efficient.
Solution in C++
#include
#include
#include
#include
using namespace std;
int main(){
string s1, s2;
getline(cin, s1);
getline(cin, s2);
int n = s1.size(), m = s2.size();
vector> dp(n+1, vector(m+1, 0));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(s1[i-1] == s2[j-1])
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
cout << dp[n][m];
return 0;
}