Coin-change counting
= Coin-change counting
Count <multisets> of allowed positive coin values whose <sum> is a target. Initialize $w(0)=1$ and $w(s)=0$ for $s>0$. For each coin $c$, update $w(s)\leftarrow w(s)+w(s-c)$ in increasing order of $s\ge c$. The outer loop over coins counts each <multiset> once while allowing repeated use of a coin.