Created
May 3, 2018 18:10
-
-
Save El-Sam/9112ccf3105044b0299b7524f49e9d9d to your computer and use it in GitHub Desktop.
A bottom top dynamic programming solution for the Coin Change problem.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| def coin_change_dp_bottom_top(amount: int, coins: set): | |
| db = [0] * (amount + 1) | |
| db[0] = 1 | |
| for coin in coins: | |
| for i in range(coin, amount + 1): | |
| db[i] += db[i - coin] | |
| return db[amount] | |
| amount = 5 | |
| coins = {1,2,5} | |
| ## coins combinations which sum to 5 | |
| # | |
| # {1,1,1,1,1} | |
| # {1,1,1,2} | |
| # {1,2,2} | |
| # {5} | |
| print(coin_change_dp_bottom_top(amount, coins)) # prints 4 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment