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.

Solving the change-making problem in Python

Solving the change-making problem in Python - Python Tutorial

From the course: Fundamentals of Dynamic Programming

Start my 1-month free trial Buy for my team

Solving the change-making problem in Python

“

- [Instructor] We solved the change making problem, by first defining a function f of i and t. This function captures the minimum number of coins needed to make target amount using only denominations d zero, up to d I. We also define the recurrence relation and how to extract the final answer from the recurrence relation. Because we don't solve every sub problem in the dependency graph, we decided we would use memoirization to implement the recurrence relation. Let's see how all this translates into Python. In this implementation, I created an inner function to represent the sub problem being solved. That way, I always have access to all the denominations as well as the cash that I can use throughout the execution. As is typical with memorization, we first check if the inputs of the sub-problem are in the cash already. If so, we can just return the cash value. But, if the value is not already cashed, we need to…

Contents