DNA Similarity

Given two DNA sequences, write an algorithm to determine their similarity. The similarity between two sequences can be determined by calculating the Longest Common Subsequence (LCS). Implement a function that takes two strings (string s1, string s2) and outputs an integer representing the similarity of the two DNA sequences. Provide a complexity analysis of your algorithm and list function test cases. The input size can reach up to 1000 characters. Example Input: ATCG TAGC Example Output: 2 Example Input ATCG TAGC