return function(
-- value to be achieved as a coin sum
target_value,
-- list of available coin values
coin_values
)
local values = { [0] = { count = 0 } }
for value = 1, target_value do
for _, coin_value in ipairs(coin_values) do
if coin_value <= value then
local count_using_coin = values[value - coin_value].count + 1
if not values[value] or count_using_coin < values[value].count then
values[value] = { count = count_using_coin, used_coin_value = coin_value }
end
end
end
end
local used_coin_values = {}
while target_value > 0 do
local used_coin_value = values[target_value].used_coin_value
table.insert(used_coin_values, used_coin_value)
target_value = target_value - used_coin_value
end
-- values may appear multiple times in the list if a coin is used multiple times
return used_coin_values
end
Given a value N
, if we want to make change for N
cents, and we have infinite supply of each of S = {S1, S2, .. , Sm}
valued coins, how many ways can we make the change? The order of coins doesn’t matter.
Let the dp[i]
be the length of the coin change of prefix N[1..i]
. Our answer is dp[N]
.
We fill dp[0]
as 1 because there is only one way to get 0 coins (We pick no coins).
Now let's try calculate dp[i]
for any i
. dp[0..i]
will store each sub problems from 0
to N
. That's why the answer will be dp[N]
. First, we need to iterate each coin types to pick them one-by-one. Then we iterate the sub problems from current coin that we pick before to N
cents. That's why we must make dp table with N
columns.
This is the codes for the Coin Change algorithm:
for coin_val in S:
for i in range(coin_val, n + 1):
dp[i] += dp[i - coin_val]
In the second iteration, for every cent that can be exchanged, we take it by subtracting the i-th column by the value of the coin we take and adding it into the current column. So dp[i]
will store the current sub problem.
O(N * S)
in any case
O(N)
- simple implementation. We only need 1D array to store the answer.
Let's say we have 3 coin types [1,2,3]
and we want to change for 7
cents. So we will define our table like this.
[1, 0, 0, 0, 0, 0, 0, 0]
0th column will store 1 since there is only one way to get 0 cents.
{1,1,1,1,1,1,1}
. On the final iteration, our table be like:[1, 1, 1, 1, 1, 1, 1, 1]
dp[2] += dp[0]
. We know that dp[0]
stored a value of 1. Thus, dp[2] will store the value of 1 + 1 = 2
. From here we know that for 2 cents, there are 2 ways {1,1}
and {2}
. And this operation will continue. Now our table be like:[1, 1, 2, 2, 3, 3, 4, 4]
4 ways to make 7 cents using value of 1 and 2. {{1,1,1,1,1,1,1}, {1,1,1,1,1,2}, {1,1,1,2,2}, {1,2,2,2}}
[1, 1, 2, 3, 4, 5, 7, 8]
So the final answer is 8. 8 ways to make change of 7 cents using all coin types. {{1,1,1,1,1,1,1}, {1,1,1,1,1,2}, {1,1,1,2,2}, {1,2,2,2}, {1,1,1,1,3}, {1,3,3}, {2,2,3}, {1,1,2,3}}