Solução Intermediário – Semana 55 – Problema 1

Para esse problema usaremos o algoritmo de troco. Defina $$dp[m]$$ como o número mínimo de tacadas para se chegar à distância $$m$$ e $$taco[i]$$ como a distância do i-ésimo taco. Então,

$$dp[m] = \begin{cases} 0 & ,\mbox{se m = 0} \\ \min\limits_{0 \leq i < N}( dp[m – taco[i]] + 1) & , \mbox{caso m > 0} \end{cases}$$

Código para melhor entendimento:

Complexidade: $$\mathcal{O}(n\cdot d)$$

https://gist.github.com/lawrencefmm/46b055d679c8ea01285f06b2ccc438cc