Algorithms, Etc.

Algorithms, Etc. by Jeff Erickson chapter on dynamic programming is great, especially that part: In a nutshell, dynamic programming is recursion without repetition. Dynamic programming algorithms store the solutions of intermediate subproblems, often but not always in some kind of array or table. Many algorithms students make the mistake of focusing on the table (because tables are easy and familiar) instead of the much more important (and difficult) task of finding a correct recurrence. As long as we memoize the correct recurrence, an explicit table isn’t really necessary, but if the recursion is incorrect, nothing works. Dynamic programming is not about filling in tables. It’s about smart recursion! http://jeffe.cs.illinois.edu/teaching/algorithms/notes/05-dy... (http://jeffe.cs.illinois.edu/teaching/algorithms/notes/05-dynprog.pdf)