[chaoxu]

probabilistic convolution tree is not much more involved. In some sense it's just multiple polynomial multiplication.

But anyway, coin change problem can be solved much faster. http://link.springer.com/article/10.1007%2Fs00453-007-0162-8

[nonsequitur]

Thanks! That paper is available on the author's website: http://gi.cebitec.uni-bielefeld.de/people/zsuzsa/papers/Algo...