[Solved]: Are there dynamic programming examples that run in exponential time?

Problem Detail: 

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