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?

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.

Log in to continue

We're a place where coders share, stay up-to-date and grow their careers.

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?

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.