6 ms·
Longest common subsequence for an arbitrary input is NP-hard: https://en.wikipedia.org/wiki/Longest_common_subsequence https://en.wikipedia.org/wiki/Longest_com
by terrabiped 2y ago
Longest common subsequence for an arbitrary input is NP-hard: https://en.wikipedia.org/wiki/Longest_common_subsequence https://en.wikipedia.org/wiki/Longest_common_subsequence
Some narrow versions of it could be optimally solved with DP, but when the constraints are lifted, you will probably have to pay for it with either exponential memory or time.
Same applies to the Knapsack problem. You can solve some variants of it with DP, but it won't generalize.
- hexomancer 2y agoI wouldn't call the case with two sequence "some narrow version". It is by far the most common instance of the problem and honestly the first thing that pops into my mind when I hear LCS, that's why I was very surprised to hear it was NP-hard but it does make sense for an arbitrary number of sequences.