Problem statement: http://www.spoj.com/problems/CRSCNTRY/
Algorithm: Dynamic Programming - Longest Common Subsequence problem.
Approach: Basically, this an LCS problem. We need to calculate the lengths of longest common subsequence of the route of Agnes and each of the routes of Tom and print the maximum among these lengths. Easy!
Time Complexity: O(d * a * t), d = no. of datasets, a = length of route of Agnes, t = length of route of Tom
No comments:
Post a Comment