We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Once you get around to understand it, this is a much better and straightforward solution IMHO. It is also more in line with the explanations given on Topcoder.
I would sum up the algorithm this way.
# Initialize an array of combination numbers for all money amounts from 0 until the target amount# For all coin values:# for all money values starting from the coin value up to the target amount:# get the number of combinations for the money value minus the coin value # add this to the number of combinations of the money value, because you can construct them just adding a coin to them
This is a more verbose version with descriptive variables, that allows you to see the algorithm in action:
importsystarget_money,coin_count=input().strip().split(' ')target_money,coin_count=[int(target_money),int(coin_count)]coins=list(map(int,input().strip().split(' ')))combinations=[1]+[0]*target_moneyforcoin_indexinrange(coin_count):print("Combinations before processing coin {}: {}".format(coins[coin_index],combinations),file=sys.stderr)formoneyinrange(coins[coin_index],target_money+1):if(combinations[money-coins[coin_index]])>0:print(" Combinations for {} added to combinations for {} : {} += {}".format(money-coins[coin_index],money,combinations[money],combinations[money-coins[coin_index]]),file=sys.stderr)combinations[money]+=combinations[money-coins[coin_index]]print("Combinations after processing coin {}: {}".format(coins[coin_index],combinations),file=sys.stderr)print("Combinations for {} : {}".format(target_money,combinations[target_money]),file=sys.stderr)print(combinations[target_money])
The Coin Change Problem
You are viewing a single comment's thread. Return to all comments →
Once you get around to understand it, this is a much better and straightforward solution IMHO. It is also more in line with the explanations given on Topcoder.
I would sum up the algorithm this way.
This is a more verbose version with descriptive variables, that allows you to see the algorithm in action:
Now for instance, for test case
it will show the process on stderr: