动态规划7：换零钱

有如下面值的硬币，兑换Z元，最少需要多少枚。
[1, 2, 5] 兑换11元

定义状态 DP(n)为兑换n元时需要的最小硬币数量

DP(n) = min(DP(n-1), DP(n-2), DP(n-5)) + 1

换成普遍的定义则为: DP(n) = min(DP(n-arr[j])) + 1 , arr为硬币面值的组合，j为硬币面值的遍历值.

DP[n] 即为所求。

初始值的定义：DP(0) = 0

function minCount(arr, total) {
    const len = arr.length;
    // 初始化保存结果的数组，长度为total+1. 并且都赋予初值total+1
    let DP = new Array(total+1).fill(total+1);

    DP[0]=0;

    for(let i = 1; i <= total; i++) {
        for(let j = 0; j < len; j++) {
            // 币值不大于兑换金额时才可兑换
            if(arr[j] <= i) {
                DP[i] = Math.min(DP[i], DP[i - arr[j]] + 1)
            }
        }
    }

    // DP中都赋初值为total+1, 倘若兑换金额无法正好凑出，则返回-1
    return DP[total] > total ? -1 : DP[total];
}

const arr = [1,2, 5];
minCount(arr, 11);