I think what you're missing is that DP is not an algorithm in itself, but rather a theorem. I also didn't knew about this for a long time. Quoting from [1, §4]

I think what you're missing is that DP is not an algorithm in itself, but rather a theorem. I also didn't knew about this for a long time. Quoting from [1, §4] > It should be stressed, here and elsewhere, that the DP functional equation > does not constitute an algorithm. It merely stipulates a certain property > that function f defined in (3) must satisfy. Indeed, in the context of Theorem > 2 the functional equation constitutes a necessary optimality condition. This > point is sometime not appreciated by students in their first encounter with DP so that is actually happening in Dijkstra's algorithm is that the DP optimality condition is being reached with a sequence of clever approximations. Another common way to reach the DP optimality condition is by recursively exploring everything with a cache, this is how compsci people usually learn about DP, and of course this can get exponential and does not apply well to big problmems. Though, both are dynamic programming at their core. > in my view, the framework of dynamic programming is not a useful way to analyze algorithms that explore a small set of states in an exponentially larger state space Well, since DP is a theorem I kinda agree, it is not how one should think about it when solving day-to-day problems. But formally DP is the reason why these algorithms work in the first place. [1]: http://matwbn.icm.edu.pl/ksiazki/cc/cc35/cc3536.pdf http://matwbn.icm.edu.pl/ksiazki/cc/cc35/cc3536.pdf