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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 最少货币数
 * @param arr int整型一维数组 the array
 * @param aim int整型 the target
 * @return int整型
 */
function minMoney(arr, aim) {
    // write code here
    if (aim < 0) return -1;
    if (aim == 0) return 0;
    let dp = new Array(aim + 1).fill(aim + 1);
    // 这里使用了代理，将原先的数组进行一个输入的拦截，如果输入的是-1则返回aim+1
    // 干！这里用代理会导致运行超时！！！！！！还是乖乖用普通的吧。。。。
    // let handler = {
    //     get: function (target, prop) {
    //         if (prop < 0) {
    //             return aim + 1;
    //         } else {
    //             return target[prop];
    //         }
    //     },
    // };
    // dpP = new Proxy(dp, handler);
    dp[0] = 0;
    for (let i = 1; i < aim + 1; i++) {
        for (let j = 0; j < arr.length; j++) {
            if(i - arr[j]>=0){
            dp[i] = Math.min(dp[i], dp[i - arr[j]]);
            }
        }
        dp[i] += 1;
    }
    return dp[dp.length - 1] > aim ? -1 : dp[dp.length - 1];
}
module.exports = {
    minMoney: minMoney,
};