Change Making Problem Tutorial - Intro to Dynamic Programming with Python 3
Tutorial on how to solve the change problem using python programming. We'll talk about the greedy method and also dynamic programming.
#Python #Tutorial #DerrickSherrill
Got the inspiration for this video from this video:
Python Interview with a Google Engineer: Coin Change
• Coin Change Problem: Python interview...
Let me know how you would code these challenges!
Join The Socials -- Picking Shoutouts Across YouTube, Insta, FB, and Twitter!
FB - / codewithderrick
Insta - / codewithderrick
Twitter - / codewithderrick
LinkedIn - / derricksherrill
GitHub - https://github.com/Derrick-Sherrill
You guys are awesome! 4540+ subscribers at the time of writing! Thanks for supporting me along the way!
*****************************************************************
Full code from the video:
Greedy Algorithm:
greedy method
def num_coins(cents):
coins = [25, 10, 5, 1]
count = 0
for coin in coins:
while cents #("angle brackets aren't allowed in YT description")= coin:
cents = cents - coin
count = count + 1
return count
print(num_coins(32))
Any Coins and Amounts:
def _change_matrix(coin_set, change_amount):
matrix = [[0 for m in range(change_amount + 1)] for m in range(len(coin_set) + 1)]
for i in range(change_amount + 1):
matrix[0][i] = i
return matrix
def change_making(coins, change):
matrix = _change_matrix(coins, change)
for c in range(1, len(coins) + 1):
for r in range(1, change + 1):
if coins[c-1] == r:
matrix[c][r] = 1
elif coins[c-1] #("angle brackets aren't allowed in YT description") r:
matrix[c][r] = matrix[c-1][r]
else:
matrix[c][r] = min(matrix[c - 1][r], 1 + matrix[c][r - coins[c - 1]])
return matrix[-1][-1]
print(change_making([1,10,25], 86))
https://github.com/Derrick-Sherrill/D...
Packages (& Versions) used in this video:
Python 3.7
*****************************************************************
Code from this tutorial and all my others can be found on my GitHub:
https://github.com/Derrick-Sherrill/D...
Check out my website:
https://www.derricksherrill.com/
If you liked the video - please hit the like button. It means more than you know. Thanks for watching and thank you for all your support!!
Always looking for suggestions on what video to make next -- leave me a comment with your project! Happy Coding!
