Are there dynamic programming examples that run in exponential time? Every example that I've seen so far constructs the top half of a matrix in a bottom-up fashion ($n^2$) from the base case and evaluates $n$ expressions to optimize each entry.
Asked By : Wuschelbeutel Kartoffelhuhn
Answered By : Juho
A well-known example is the Held-Karp dynamic programming approach to solving the traveling salesman problem (TSP), running in $O(n^22^n)$ time and $O(n2^n)$ space. For more, see these notes.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/22094
0 comments:
Post a Comment
Let us know your responses and feedback