题解 | 兑换零钱(一)

/**
 * 最少货币数
 * @param arr int整型一维数组 the array
 * @param aim int整型 the target
 * @return int整型
 */
function minMoney(arr, aim) {
    // 初始化 dp 数组，大小为 aim + 1
    let dp = new Array(aim + 1).fill(Infinity); // 使用 aim + 1 作为初始值
    dp[0] = 0; // 组成金额 0 所需的货币数为 0

    // 遍历每个面值
    for (let i = 0; i < arr.length; i++) {
        // 遍历每个金额 j，从 arr[i] 到 aim
        for (let j = arr[i]; j <= aim; j++) {
            // 更新 dp[j]
            dp[j] = Math.min(dp[j], dp[j - arr[i]] + 1);
        }
    }

    // 如果 dp[aim] 仍然为初始值，说明无法组成目标金额
    return dp[aim] === Infinity ? -1 : dp[aim];
}

module.exports = {
    minMoney: minMoney
};