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.
For further actions, you may consider blocking this person and/or reporting abuse
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.