题解 | #兑换零钱(一)#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 最少货币数
 * @param arr int整型一维数组 the array
 * @param aim int整型 the target
 * @return int整型
 */
function minMoney( arr ,  aim ) {
    // write code here
    let len = arr.length;
    let dp = Array.from({length:aim+1},()=>Infinity);
    dp[0] = 0;
    //动态规划：
    //dp[i]表示兑换i面值需要兑换的最小次数
    //当前需要找的面额为i，当前的零钱arr[j]；
    // dp[i-arr[j]]则表示减去当前零钱值得最小次数
    // dp[i-arr[j]]+1则表示加上当前零钱的最小次数
    //所以状态转移方程就是：dp[i] = Math.min(dp[i],dp[i-arr[j]]+1)
    for(let i = 1;i<=aim;i++){
        for(let j=0;j<len;j++){
            if(arr[j]<=i){//当前需要兑换的钱需要大于零钱才行，不然兑换不了
                dp[i]= Math.min(dp[i],dp[i-arr[j]]+1)
            }
        }
    }
    return dp[aim]===Infinity?-1:dp[aim]
}
module.exports = {
    minMoney : minMoney
};