# Longest Common Subsequence using Dynamic Programming

In this CPP tutorial, we are going to discuss how to find the length of a maximum common subsequence of two strings. Finding the Longest Common Subsequence using Dynamic Programming will be a much better practice for us.

**What is Subsequence?**

A Sub-sequences is a sequence that appears in same relative order, but not necessarily contiguous.

for example :- ** ‘a’, ‘b’, ‘c’, ‘ab’, ‘bc’, ‘abc’** are some Sub-sequence of string **“abc”.**

**Why Dynamic Programming?**

We can solve the same problem by simple recursive method but time complexity for this approach is exponential. In the worst case, it will be O ( 2^n ). Instead of calculating for the same sub-problem, again and again, we prefer to use a dynamic programming approach and store the result of every sub-problem which reduces the time complexity into linear.

### Algorithm to find Longest Common Subsequence in C++

- Input two strings S1, S2 of length m and n whose sub-sequence to be found.
- Now, fill up the table dp[m+1][n+1] in bottom-up manner.
- If character of both string matches then fill the value in dp[][] table by 1+(dp[][] value in previous diagonal )

dp[i][j] = 1+dp[i-1][j-1]

- if character of both strings does not matches then, fill the value in dp[][] table as maximum of left or upper value in dp[][] table.

dp[i][j] = max ( dp[i-1][j], dp[i][j-1] )

- Now, value in dp[m][n] stores our result for longest common sub-sequence of string S1, S2.

### C++ Code to find the longest common subsequence of two strings

#include<bits/stdc++.h> #define for(i,a,b) for(int i=a;i<b;i++) using namespace std; typedef long long ll; void solve(string s1, string s2, ll m, ll n) { int dp[m+1][n+1]; for(i,0,m+1) { for(j,0,n+1) { if (i == 0 || j == 0) dp[i][j] = 0; else if(s1[i-1]==s2[j-1]) dp[i][j]=1+dp[i-1][j-1]; else dp[i][j]=max(dp[i-1][j],dp[i][j-1]); } } cout<<dp[m][n]<<endl; } int main() { string s1,s2; cin>>s1>>s2; ll m,n; m=s1.length(); n=s2.length(); solve(s1,s2,m,n); }

**Input **

Codespeedy Codersite

**OUTPUT**

6

As the longest common sub-sequence among the above two input strings is Codese.

also, learn:

## Leave a Reply