Após explicitar o entendimento do problema lhes apresentei três soluções. Uma iterativa, uma recursiva e uma utilizando técnicas de programação dinâmica. A primeira abordagem é esperada de qualquer aluno da graduação. A segunda requer conhecimento de recursividade, já a terceira envolve um paradigma que não é tão trivial. Segundo o entrevistador, ganhei pontos ao apresentar a solução utilizando DP.