3 ms·

Trust me, Norvig knows about the difference.

• eru 17y ago
  Yes, but I also expected something about dynamic programming. Norvig's title leads to confusion. (Or rather the older usage of the term is not very well thought-out, and should probably be replaced with "solving problems by solving all smaller problems". Alas, the other guys came first.) Interestingly there are some nice patterns in implementing dynamic programming --- especially in relation to memoization and lazy evaluation. I should probably write an article with the same title.
  • 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 ago
      Perhaps 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.
• viraptor 17y ago
  Does it mean he can use them in a confusing way?
• j_baker 17y ago
  It's not whether norvig knows the difference or not. It's whether the person who's reading the title knows the difference.