Annettuna on n kolikkoa ja summa x. Laske, monellako tavalla summa x voidaan muodostaa kolikoista niin, että kolikoiden määrä on pienin mahdollinen.
Voit olettaa, että 1 \le n \le 10 ja 1 \le x \le 100. Yksi kolikoista on aina arvoltaan 1. Algoritmisi tulee toimia tehokkaasti kaikissa tapauksissa.
Toteuta tiedostoon minways.py funktio count, joka palauttaa tehtävän vastauksen.
def count(x, coins):
# TODO
if __name__ == "__main__":
print(count(5, [1])) # 1
print(count(5, [1, 2, 3, 4])) # 4
print(count(13, [1, 2, 5])) # 12
print(count(42, [1, 5, 6, 17])) # 30
Selitys: Kun x=5 ja kolikot ovat [1,2,3,4], mahdolliset tavat ovat [1,4], [2,3], [3,2] ja [4,1]. Tapojen määrä on 4.