In how many ways can you change a $50 bill using $20 bills, $10 bills, $5 bills, $2 bills, and $1 bills ?
I don't know the answer
To find the number of ways to change a $50 bill using different denominations of bills, we can approach the problem using Dynamic Programming.
We can define an array, let's call it "dp," where dp[i] represents the number of ways to change the amount i using the given set of bills.
To calculate dp[i], we can use the following recurrence relation:
dp[i] = dp[i - 20] + dp[i - 10] + dp[i - 5] + dp[i - 2] + dp[i - 1]
We initialize dp[0] = 1, which means there is one way to make change for $0 (i.e., not using any bills).
Now, let's calculate dp[i] for i = 1 to 50 using the recurrence relation mentioned above.
dp[1] = dp[0] = 1
dp[2] = dp[1] = 1
dp[3] = dp[2] + dp[1] = 1 + 1 = 2
dp[4] = dp[3] + dp[2] + dp[1] = 2 + 1 + 1 = 4
dp[5] = dp[4] + dp[3] + dp[2] + dp[1] = 4 + 2 + 1 + 1 = 8
dp[6] = dp[5] + dp[4] + dp[3] + dp[2] + dp[1] = 8 + 4 + 2 + 1 + 1 = 16
...
dp[50] = dp[49] + dp[48] + dp[45] + dp[48] + dp[49] = ... = 31824
Therefore, there are 31,824 ways to change a $50 bill using $20 bills, $10 bills, $5 bills, $2 bills, and $1 bills.
well, just start listing them:
20, 20, 10
20, 20, 5, 2, 2, 1
20, 20, 5, 2, 1, 1, 1
and so on.
At each step, substitute smaller bills for larger ones.
Without going through the whole list, you should see a pattern in how many new ways come from replacing a bill with smaller ones.