Another Monday is upon us, and another batch of links is due. This week I’m going to focus on Dynamic Programming (or DP for short). The reason is that upcoming Project Euler problems are DP- and memoization heavy. Another reason is that DP problems are quite popular, so it’s definitely a good skill to have.
After you’ve read that, you should take a look at Bruce Merry‘s introduction to Dynamic programming. It’s got a really great step-by-step approach to solving a DP problem, which in my experience works quite well.
Now you should have a good idea of how DP works. Next I suggest you go over these Dynamic Programming Practice Problems presented by Brian C. Dean. These are good video tutorials covering a few common DP problems.
Now you should be able to solve some real DP problems. A great list of DP problems is the Dynamic Programming Problem Set on the Timus Online Judge. Start with the easiest problem (the problems are sorted by difficulty, and the easiest is the topmost problem). Read the problem description and then use Bruce Merry’s step-by-step approach (from above) to solve it. Don’t worry if you can’t, DP is a tough nut to crack and the only way to become good at it is to practice and practice.
One more DP link I think I should mention is our own collection of DP problems: MathBlog posts tagged with “Dynamic Programming”. Kristian has solved many Project Euler problems with DP, and he always manages to explain his method well.
I really think I need to have one extra link for those of you who don’t find the above links interesting. Haskell is a functional programming language every mathematical programmer should know. It’s also insanely beautiful. The final link is a book about Haskell: Learn You a Haskell for Great Good!. I’m currently on the 12th chapter (of 14) and it’s been great to read. The author allows you to read it online, free of charge, but the book can also be purchased to support the author.