From the course: Fundamentals of Dynamic Programming

Planting flowers in a flowerbox - Python Tutorial

From the course: Fundamentals of Dynamic Programming

Start my 1-month free trial Buy for my team

Planting flowers in a flowerbox

“

- [Instructor] One problem where dynamic programming is useful is the flowerbox problem. In the flower box problem, we have some soil with a few places to plant flowers. Each place we can plant a flower has some amount of nutrients, which we'll call visa V sub i. For example, the first location has three units of nutrients, the next location has 10 and so on. If you plant a flower in one of these locations the height of the flower will be proportional to the quantity of nutrients at that location. If you plant the flower at the very left and the flower will grow three units. So here are the rules. You can plant as many flowers as you want as long as they're not right next to each other. Otherwise the flowers will compete for nutrients. Your goal is to maximize the total height of all the flowers that you plant. Let's look at how that plays out in our example. What we wana do is plant flowers where the V sub i are 10 and two. This results in a total height of 12 units, try it for yourself. Any other valid configuration leads to a smaller total height. It might seem like this problem is pretty easy. Start with the location with the most nutrients and then go from there, right? Well, what about in this example, a 10 surrounded by two nines? Here, the best option is actually to plant in the two locations with nine units of nutrients in them and completely ignore the middle location altogether. So it seems the greedy approach that is taking the most nutrients at the beginning doesn't work. On the other extreme, we could try every valid configuration but there will be too many options to try. Luckily, there is a middle ground and dynamic programming will help us take advantage of that approach.

Contents