Hacker News Reader

Longest common subsequence can be solved in at most quadratic time via dynamic programming.

Longest common subsequence for an arbitrary input is NP-hard: 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.

I 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.

Reply on news.ycombinator.com