NC126 换钱的最少货币数

解法

function minMoney( arr ,  aim ) {
    let dp = new Array(aim + 1).fill(Number.MAX_SAFE_INTEGER)
    dp[0] = 0
    
    for(let i = 1; i < aim + 1; ++i){
        for(let j = 0; j < arr.length; ++j){
            if(i >= arr[j]){
                dp[i] = Math.min(dp[i], dp[i - arr[j]] + 1)
            }
        }
    }
    
    if(dp[aim] === Number.MAX_SAFE_INTEGER){
        return -1
    }
    return dp[aim]
}

解析

这种涉及前后状态的题目用dp会比较简单，dp[i]表示金额i所需要的最小货币数目，显然dp[0] = 0(0元钱当然不需要或货币)。然后便利dp数组，通过前面确定的状态退出后面的状态（比如dp[0]=0）。对于每个金额都便利一次arr数组，确保使用张数最少。对于每个金额 当前使用的纸币数量 =（当前的金额 与 当前的货币面值 的差所需要的纸币数量） + 1