Seria interessante que não o postasses logo, pois, este problema foi aqui postado por mim com dois própositos:
1. Trazer mais gente para o Python
2. Introduzir o conceito de Programação Dinâmica que eu próprio também estou a aprender
Reparei que a Adriana também veio ler o tópico.

Seria interessante e muito mais útil para todos (eu incluído) que discutissem aqui entre vocês algumas formas de abordar este problema (não necessariamente por programação dinâmica) e que descobrissem alguns aspectos interessantes sobre ele. O papel e o lápis são sempre os vossos melhores aliados nestes casos

Discutam todas as formas possíveis de resolver a questão, conjecturem sobre a validade e eficiência das mesmas, e no fim, irão aprender uma técnica de design de algoritmos espectacular!!

Bom brainstorming!!