最小硬币找零问题是硬币找零问题的一个变种。硬币找零问题是给出要找零的钱数，以及可以用的硬币面额d1...dn及其数量，找到所需最小硬币个数。
例如，美国有以下面额硬币:d1=1,d2=5,d3=10,d4=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浏览器中的运算结果
