518. 零钱兑换 II - 从缓存到二维dp到一维dp

李恒道

https://leetcode.cn/problems/coin-change-ii/description/

首先我们可以设计一个缓存

假设到了某一个数字，如果当前数字已经小于了金额，则跳过该数字

如果当前数字大于金额，则存在两种可能

1.放弃该数字，继续往前走

2.挑选一个数字，然后扣减金额，继续在该数字上停留

则可以写出

var change = function (amount, coins) {
    const cache = new Map()
    const dfs = (amount, pos) => {
        if (amount == 0) {
            return 1
        }
        if (amount < 0) {
            return 0
        }
        if (pos >= coins.length) {
            return 0
        }
        const flag = `${amount} ${pos}`
        if (cache.has(flag)) {
            return cache.get(flag)
        }
        let result = undefined
        if (amount < coins[pos]) {
            result = dfs(amount, pos + 1)
        } else {
            result = dfs(amount, pos + 1) + dfs(amount - coins[pos], pos)
        }
        cache.set(flag, result)
        return result
    }
    return dfs(amount, 0)
};

那我们现在开始转成动态规划，有两维，一维是金额，一维是硬币，边界时金额为0时则存在一种，同时为了防止边界溢出我们要稍加一点数组

var change = function (amount, coins) {
    const dp = new Array(coins.length + 1).fill(0).map(() => new Array(amount + 1).fill(0))
    for (let index = 0; index < dp.length; index++) {
        dp[index][0] = 1
    }
    for (let index = dp.length - 2; index >= 0; index--) {
        for (let mount = 1; mount <= amount; mount++) {
            if (mount < coins[index]) {
                dp[index][mount] = dp[index + 1][mount]
            } else {
                dp[index][mount] = dp[index + 1][mount] + dp[index][mount - coins[index]]
            }
        }
    }
    return dp[0].pop()
};

到这里我们可以看到，每一维度仅与上一层和本层金额稍少的位置

那就可以将二维转化成一维，一层一层往上递归，同时又可以发现

我们对硬币从前往后递归和从后往前递归都无所谓

因为每次递归的时候只考虑该层之前的层数存在的可能数

无论硬币数是[1,2,5]还是[5,2,1]都不会影响答案

那我们可以写出

const change = function (amount, coins) {
    const dp = Array(amount + 1).fill(0)
    dp[0] = 1
    for (const coin of coins) {
        for (let mount = 1; mount <= amount; mount++) {
            dp[mount] = dp[mount] + (mount < coin ? 0 : dp[mount - coin])
        }
    }
    return dp.pop()
}

将边界略微精简即可得到官解的答案

王一之