3 ms·
"[S]olving problems by solving all smaller problems" is really just plain ol' divide-and-conquer. What makes dynamic programming algorithms different, although
by scott_s 17y ago
"[S]olving problems by solving all smaller problems" is really just plain ol' divide-and-conquer. What makes dynamic programming algorithms different, although a subset of, divide-and-conquer algorithms is that intermediate solutions are stored for later use.
- eru 17y agoPerhaps I should have been more cleary. I meant that Dynamic Programming solves _all_ smaller problems. Divide-and-Conquer only solves smaller problems that come up as a part of the bigger problems. So e.g. quicksort sorts sublists. A hypothetic dynamic programming solution would first sort _all_ conceivable lists of length 1, then use that to solve all lists of length 2, and so on. But your distinction may come into it as well. Though you can also use memoization in Divide-and-conquer.