loading...

Discussion on: Learn Dynamic Programming using Fibonacci as an example

Collapse
curtisfenner profile image
Curtis Fenner

This is a nice explanation of DP and its application to the Fibonacci numbers specifically, but I really don't like the Fibonacci numbers being used as a way to introduce DP, for a few reasons.

First, because some version of (3) is easy to come up without knowing DP, and isn't really a DP solution.

Second, because DP isn't the fastest way to solve the Fibonacci numbers problem. You can do it in O(log n) time and constant memory through exponentiation-by-squaring of a 2x2 matrix!


I think the best problems that get at the "meat" of dynamic-programming take in arrays and not just numbers. That way, there's never any special formula to guess at, and the way the problem is "recursive" becomes more obvious. Here's a couple:

  • You're playing a game like Candy Land. Each turn, you roll a die and move that number of tiles forward. However, some of the tiles are X'd out, and you're not allowed to move to them. (Instead, you roll again). Given a board as a list of TRUE/FALSE tiles (FALSE meaning you cannot move to it), how many distinct paths are there from the first tile to the last tile?

  • Your favorite ice cream parlor is having a month-long promotion. Each day, they have a different special which costs a different amount. You have a loyalty punch card that after K purchases you get a free ice cream! (But, you can wait to use it for a more expensive ice cream if you want). Given a list of the prices each day and K, what is the least money you can spend to get every special ice cream?

Collapse
rattanakchea profile image
Rattanak Chea Author

This post was meant to be build a foundation for DP concepts. Thus the simpler the example, the easier to understand. I like your two questions a lot and those are practical for technical interview. I will spend time and work on those next.

Do you have a favorite book/resource on learning DP/algorithms? Besides the obvious: Leetcode, Cracking the coding interview.