Algorithm Name
Longest Common Subsequence
Programming Language
C++
Category
Dynamic Programming
Difficulty Level
Medium (Intermediate)
Algorithm Description
The Longest Common Subsequence (LCS) problem is a classic Dynamic Programming problem.
Given two sequences, the goal is to find the length (and optionally the sequence) of the longest subsequence that appears in both sequences in the same relative order (not necessarily contiguous).
Steps:
Define a 2D DP table dp[i][j] representing the LCS length of the first i characters of string A and the first j characters of string B.
Recurrence:
If A[i-1] == B[j-1], then dp[i][j] = 1 + dp[i-1][j-1].
Else, dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
Initialize first row/column as 0 (base case).
The final answer is dp[m][n], where m and n are the lengths of the two sequences.
This approach runs in O(m × n) time with O(m × n) space. It can also be optimized to use only two rows of DP for space efficiency.
References (Optional)
No response
Contribution Intent
Code of Conduct
Algorithm Name
Longest Common Subsequence
Programming Language
C++
Category
Dynamic Programming
Difficulty Level
Medium (Intermediate)
Algorithm Description
The Longest Common Subsequence (LCS) problem is a classic Dynamic Programming problem.
Given two sequences, the goal is to find the length (and optionally the sequence) of the longest subsequence that appears in both sequences in the same relative order (not necessarily contiguous).
Steps:
Define a 2D DP table dp[i][j] representing the LCS length of the first i characters of string A and the first j characters of string B.
Recurrence:
If A[i-1] == B[j-1], then dp[i][j] = 1 + dp[i-1][j-1].
Else, dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
Initialize first row/column as 0 (base case).
The final answer is dp[m][n], where m and n are the lengths of the two sequences.
This approach runs in O(m × n) time with O(m × n) space. It can also be optimized to use only two rows of DP for space efficiency.
References (Optional)
No response
Contribution Intent
Code of Conduct