3 ms·
probabilistic convolution tree is not much more involved. In some sense it's just multiple polynomial multiplication. But anyway, coin change problem can be so
by chaoxu 11y ago
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 http://link.springer.com/article/10.1007%2Fs00453-007-0162-8
- nonsequitur 11y agoThanks! That paper is available on the author's website: http://gi.cebitec.uni-bielefeld.de/people/zsuzsa/papers/Algorithmica_BL_2007.pdf http://gi.cebitec.uni-bielefeld.de/people/zsuzsa/papers/Algo...