最小硬币找零问题是硬币找零问题的一个变种。硬币找零问题是给出要找零的钱数，以及可以用的硬币面额d₁...d_n及其数量，找到所需最小硬币个数。
例如，美国有以下面额硬币:d₁=1,d₂=5,d₃=10,d₄=25。
如果要找36美分的零钱，我们可以用1个25美分，1个十美分和一个一美分。

这类问题属于动态规划一类的问题，最简单的方法是利用递归的思路来做（也可以用栈来做，但是比较麻烦），解决方案是找到对应每个x<n的解，比如说我们要求36美分的找零方案，可以先求35美分，34美分，31美分...1美分的解，将解建立在更小值的解的基础上。

下面是代码：

function MinCoinChange(coins) {
    var coins=coins;
//MinCoinChange接收Coin类的参数，代表问题中的面额。对于美国的硬币系统而言，他们是[1,5,10,25]。我们可以传入任何参数
    var cache={}
//cache用来缓存计算结果，避免重复计算

    this.makechange=function(amount){//递归函数，解决找零问题
        var me=this;
        if(!amount){return [];}//若amount不为正，返回空函数
        if(cache[amount]){return cache[amount];}//检查cache缓存，如果结果已经计算过，那么就直接返回结果，否则继续计算
        
        var min=[];//min用来存储amount的找零结果

        for(var i=0;i<coins.length;i++)
        {
            var coin=coins[i];//依次尝试每种面额
            var newAmount=amount-coin;//计算新的找零面额
            
            if(newAmount>=0){
                var newMin=me.makechange(newAmount);//计算新的找零面额的找零方案
            }

            if(newAmount>=0 &&(newMin.length<min.length-1 || !min.length)&&(newMin.length || !newAmount)){
//依次判断newAmount是否有效，新的最小硬币数是否是最优解，与此同时newMin和newAmout的值是否是合理的值，如果以上判断都成立，意味着有一个更优的答案，比方说找零一个五美分，可以给五个一美分，也可以给一个五美分，而一个五美分是最优解。
                min=newMin.concat(coin);
                console.log('new Min'+min+'for'+amount);
            }
        }
        return (cache[amount]=min);
    }
}

计算36美分的找零方案：

var minCoinChange=new MinCoinChange([1,5,10,25]);
minCoinChange.makechange(36)

结果:

Chrome浏览器中的运算结果