Esse é outro problema de programação dinâmica, uma variação do problema clássico do troco, sendo que nesse caso queremos mínimizar o número de moedas (ou nesse problema, tacadas).
Para esse problema vamos considerar a $$dp_i$$, a quantidade mínima de tacadas para chegar no valor $$i$$, $$inf$$ caso seja impossível.
Temos a seguinte recurção:
- Caso $$i = 0$$, caso base $$dp_i = 0$$
- Caso $$i < 0$$, caso em que é impossível chegar a 0, $$dp_i = inf$$
- Caso $$i > 0$$, podemos colocar qualquer moedas, então $$dp_i = \min\limits_{i=1}\limits^n(dp_{i-c_i} + 1)$$
A partir disso fazemos a recursão partindo da distância máxima, para achar o mínimo de tacadas partindo do $$0$$, caso impossível podemos calcular uma dp semelhate a acima ou podemos somente ver se $$dp_m = inf$.
Código para melhor entendimento:
OBS: O código enviado esqueceu de fazer a memorização na dp que achava o mínimo, então corrigi isso.
https://gist.github.com/fredbr/51f160ce4c2ee47c7a055dcde9867d36