I am trying to wrap my head around how dynamic programming helps avoid all possibilities that are exponential after reading Chapter 8 NP-complete problems of Algorithms by Dasgupta et al. where it says:
So far in this book we have seen the most brilliant successes of this quest, algorithmic techniques that defeat the specter of exponentiality: greedy algorithms, dynamic programming, linear programming (while divide-and-conquer typically yields faster algorithms for problems we can already solve in polynomial time).
Going back to Chapter 6 Dynamic programming, I followed along the longest increasing subsequence problem that this video also shows how to solve. It seemed to me that we were considering all other choices in the solution for the sequence $3, 4, -1, 0, 6, 2, 3$, but only did this with $n^2$ time.
What are the other possible subsequences that would reveal that this problem is exponential in nature without dynamic programming? I can see that in the
0-1 Knapsack problem there are $2^n$ possibilities to consider but can't see the exponential counterpart of the
longest increasing subsequence problem.