4 ms·
> Dynamic programming. Only recently has it been shown that, unless P=NP, O(n^2) is basically optimal. [6] This is about a dynamic programming approach to the
by jstimpfle 9y ago
> Dynamic programming. Only recently has it been shown that, unless P=NP, O(n^2) is basically optimal. [6]
This is about a dynamic programming approach to the edit distance problem. Not dynamic programming itself, which is a vague term (I think it's basically "use a bottom-up approach and avoid doing the same work twice")
- opportune 9y agoYep. It's a complete oversimpliification to consider all DP problems at O(n^2). Anybody familiar with modern algorithms will tell you that certain DP problems can even be O(nloglogn)! https://en.wikipedia.org/wiki/Van_Emde_Boas_tree https://en.wikipedia.org/wiki/Van_Emde_Boas_tree For example, implementing VEB trees or even (countably distinct length) dictionary-based tries can speed up execution by orders of logn/n