When I copy&paste your code into my editor, it immediately greets me with 81(!!!) errors and warnings. To be fair, some of these are duplicates, because I have multiple linters configured. However, about 20 of those are real.
PEP8 violations
The standard community coding style for the Python community is defined in Python Enhancement Proposal 8 – Style Guide for Python Code. You should always follow the guidelines of PEP8. There are plenty of tools available that can flag and even auto-correct violations of PEP8.
Here's just a couple that my editor flagged (and auto-corrected automatically, so I didn't have to do a single thing):
- Space after comma: Pretty much everywhere where you use a comma, you squish everything together without whitespace. You should have a space after the comma.
- Space around operators: You should have whitespace on both sides of a binary infix operator. Sometimes you do that, sometimes you don't, e.g. here
[c for c in coins if c<=n]
- Indentation should be 4 spaces. You use 5 spaces for the first level of indentation, then 3 spaces for the second level except in the
elif where you use 7.
- You have 2 blank lines before the
else:. In general, spacing with a function should only be 1 blank line.
- You have 1 blank line after the function. There should be 2 blank lines after a function or class.
- Docstring: Your function should have a docstring explaining its usage. (Note: all the above violations were automatically fixed by my editor, this is the only one that couldn't be auto-corrected.)
Consistency
It is very important to be consistent. When people read your code, and you do the same thing two different ways, they will automatically assume that you want to tell them something, that the difference is somehow meaningful.
I mentioned a couple of inconsistencies above, e.g. the fact that you sometimes use whitespace around operators and sometimes don't.
Even if you don't believe in style guides, you should at least be consistent with yourself.
Linter
You should use a linter, preferably one with an auto-correct functionality. When I hit "Save" in my editor, of the 81 errors and warnings I mentioned earlier, 78 get fixed automatically, leaving only 3 (of which one is a duplicate, because as I mentioned, I have multiple linters configured).
As mentioned above, the only PEP8 violation that couldn't be auto-corrected is the missing documentation.
The other remaining issue is something already mentioned in hjpotter92's answer: since you return directly from the if, there is no need for the elif. Once I remove the el, I get a new issue telling me the same thing for the else.
Redundant statement
In the first if, you assign to known_results[n] but then immediately return 1. Since the return ends the execution of the function, and known_results is local to the function, there is no way that this variable can be used any further, therefore the assignment is unnecessary and can just be removed.
Redundant assignment
Also, as mentioned in hjpotter92's answer, the two assignments in the if branch inside the for loop can be chained.
Truthiness / falsiness
In elif condition, you check whether known_results[amount] is greater than 0. Since you initialize it with zero, and only ever add to it, what you are semantically doing is basically checking whether you have ever put a value in. In Python, 0 is a false value, so instead of checking for known_results[amount] > 0, you could simply check for known_results[amount].
Naming
n and c are not very descriptive names. Try to find names that better reveal the intent of those variables. For example n might be renamed to amount and c to coin.
In fact, you wrote in your comment under the question:
n is the amount you have to generate coin change for.
If you have to write a comment like this, either in code or in this case under the code, that is a good sign that the name is not good enough. If you have to say something like n is the amount, that is a good indication that n should be called amount, because then you wouldn't have to explain that it is the amount!
i would be acceptable for an index in a loop, but it isn't an index here. It is an element of a collection, not an index into a collection or a loop index. Actually, it could again be called coin, although that might be confusing.
Thinking about it, maybe coins should be called denominations and c should then be denomination.
Also, I would expect a function called coin_change to compute the actual coins for the change, not simply the number of coins.
Datatypes
Since it doesn't make sense to specify the same denomination multiple times, and the order of the denominations doesn't matter, the denominations could be a Set (or even a FrozenSet since it is never mutated) rather than a List.
Or, does the order matter? It is actually not clear, and could benefit from some documentation if it does indeed matter.
Likewise, known_results probably makes more sense to be a defaultdict.
Type Annotations
Python 3 supports (function) type annotations since the very first release in 2008 and variable annotations for a while. In more recent times, the typing module with predefined types has been added. Also, there is the Mypy static type checker for Python.
It is a good idea to take advanced of these tools, even if just for documentation.
API
known_results is a private internal implementation detail of your (recursive) implementation. It is an accumulator whose only purpose is to keep state in your recursive calls. It shouldn't be part of the public API, you shouldn't force the caller to know what to pass here as an argument.
At the very least, you should make it an optional parameter with a default argument, so that the caller doesn't have to pass it:
def minimum_number_of_coins_for_change(amount: int, denominations: Set[int]) -> int:
def minimum_number_of_coins_for_change_rec(
amount: int, known_results: DefaultDict[int, int]
) -> int:
pass # …
However, the main reason why we pass the accumulator as an argument in a recursive function when we do functional programming is that in functional we are not allowed to mutate state, and thus the arguments on the function call stack are one of the very few places where we can keep state. However, you are mutating known_results anyway, so we don't have to pass it along as an argument, it is enough to define it outside of the recursive function:
def def coin_change(amount, denominations, known_results=[0] * (amount + 1)):
But actually, you shouldn't even give the caller a chance to accidentally pass the wrong argument. It is better to remove it from the parameter list completely.
The standard way of introducing an additional parameter just for purposes of state-keeping during recursion is to introduce a new nested function for the recursion, and call that from the outer function with the correct argument. Something like this:
def minimum_number_of_coins_for_change(amount: int, denominations: Set[int]) -> int:
known_results: DefaultDict[int, int] = defaultdict(int)
def minimum_number_of_coins_for_change_rec(amount: int) -> int:
min_coins = amount
if amount in denominations:
return 1
if known_results[amount]:
return known_results[amount]
for coin in [
denomination for denomination in denominations if denomination <= amount
]:
count = 1 + minimum_number_of_coins_for_change_rec(
amount - coin
)
if count < min_coins:
known_results[amount] = min_coins = count
return min_coins
return minimum_number_of_coins_for_change_rec(amount)
denominations: Set[int] = {1, 2, 3}
amount = 5
print(minimum_number_of_coins_for_change(amount, denominations))
Unfortunately, there are now still two PEP8 violations in the code: too long lines. I will leave them in here, since there are multiple different ways to tackle this, one of which is better names, which I will leave to you.
API, pt. 2
It seems to me that the amount you want to compute change for changes much more often than the denominations. So, it could make sense to have a coin_changer object with specific denominations that can then compute change for those denominations multiple times. Something like this:
from collections import defaultdict
from typing import DefaultDict, Set
class CoinChanger:
def __init__(self, denominations: Set[int]):
self.denominations = denominations
def minimum_number_of_coins_for_change(self, amount: int) -> int:
known_results: DefaultDict[int, int] = defaultdict(int)
def minimum_number_of_coins_for_change_rec(amount: int) -> int:
min_coins = amount
if amount in self.denominations:
return 1
if known_results[amount]:
return known_results[amount]
for coin in [
denomination
for denomination in self.denominations
if denomination <= amount
]:
count = 1 + minimum_number_of_coins_for_change_rec(amount - coin)
if count < min_coins:
known_results[amount] = min_coins = count
return min_coins
return minimum_number_of_coins_for_change_rec(amount)
denominations: Set[int] = {1, 2, 3}
amount = 5
coin_changer = CoinChanger(denominations)
print(coin_changer.minimum_number_of_coins_for_change(amount))
At the very latest now that we have turned our code into a module containing a class, we should make sure that the test code at the bottom does not accidentally get executed just because someone imported the module. In general, such code should always be wrapped into a __main__ guard:
if __name__ == '__main__':
denominations: Set[int] = {1, 2, 3}
amount = 5
coin_changer = CoinChanger(denominations)
print(coin_changer.minimum_number_of_coins_for_change(amount))
Although ideally, it shouldn't be there at all, it should be a proper unit test in a separate test module. (And there should be more tests, including corner cases such as empty denominations, an amount of 0, negative amounts, combinations of amounts and denominations where giving change is impossible, etc.)
nis the amount you have to generate coin change for. \$\endgroup\$