not homework... something i find an interesting problem

[bearophileHUGS at lycos.com]

MRAB:
> I think I might have cracked it:
> ...
>      print n, sums

Nice.
If you don't want to use dynamic programming, then add a @memoize
decoration before the function, using for example my one:
http://code.activestate.com/recipes/466320/

And you will see an interesting speed increase, even if you don't use
Psyco ;-)

Bye,
bearophile