Pienimmät määrät

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$.