From the course: Fundamentals of Dynamic Programming

Unlock this course with a free trial

Join today to access over 22,600 courses taught by industry experts.

Breaking down the change-making problem into subproblems

Breaking down the change-making problem into subproblems - Python Tutorial

From the course: Fundamentals of Dynamic Programming

Start my 1-month free trial Buy for my team

Breaking down the change-making problem into subproblems

“

- [Instructor] Let's summarize our goal in the change making problem. We have some denominations of coins that we can use, using as many of each denomination as we want. We want to use the fewest total number of coins, to add up to our target. Here, the best option is to use three five cent coins and one one cent coin. In general, the greedy approach of picking the highest denomination doesn't always work. So what do we do instead? As is typical in dynamic programming problems, we have a choice. On one hand, we can say 12 cent coins are still on the table and we'll use a single 12 cent coin. Now, our target is only four cents and we still have all the same denominations available to us. Of course, we can't actually use another 12 cent coin after this, but that's a choice we can face later. On the other hand, we can choose to stop using 12 cent coins altogether. Now, we need to make 16 cents still. But our…

Contents