Could we say that Dynamic programming is nothing but recursion + Memoization?
Although the formal definition of dynamic programming is that the problem should have an optimal substructure property, which in a way is nothing else but recursion.
$\begingroup$
$\endgroup$
2
-
$\begingroup$ cs.stackexchange.com/q/99513/755, cs.stackexchange.com/q/2644/755, cs.stackexchange.com/q/47216/755, cs.stackexchange.com/q/2057/755 $\endgroup$– D.W. ♦Commented Sep 3, 2022 at 17:31
-
$\begingroup$ Yes, "Dynamic programming=Recursion + Memoization". It sounds simple (and often is), but sometimes the problem is to come up with recursion so that DP is efficient. E.g., for Hamiltonian path, naive DP will give you $\tilde O(n!)$ time, while with a certain optimization it becomes $\tilde O(2^n)$. Do check the links above. $\endgroup$– DmitryCommented Sep 4, 2022 at 1:12
Add a comment
|