Are there dynamic programming examples that run in exponential time? 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.
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.