This book has about 26 pages dedicated to Dynamic Programming (the remaining 36 pages in the chapter detail different exercise problems but I'm sure are just as

This book has about 26 pages dedicated to Dynamic Programming (the remaining 36 pages in the chapter detail different exercise problems but I'm sure are just as educational). I think a strong foundation in recognizing the recurrence is key to becoming better at Dynamic Programming. If you're not able to first see the recurrence, then you're doomed to rote-learn a la videos on youtube where the main focus is table filling (I'm looking at you, Tushar Roy). Here's a snippet from the DP chapter in Erickson's book: > 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 (and instructors, and textbooks) 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 recurrence is incorrect, we are well and truly hosed. On a quick skim of the chapter, here's what it offers that other traditional book chapters don't: * Progressive optimization of memoized solutions. The example used is Fibonacci where each recurrence is cached, then it's transformed into an iterative for-loop based solution where a table/array is filled, and finally 2 variables are used instead of the whole array to store intermediate solutions. * Dynamic Programming on trees (both as a datastructure for storing intermediate solutions and sometimes as a problem ex: Optimal BST construction)