518. 零钱兑换 II - 从缓存到二维dp到一维dp
https://leetcode.cn/problems/coin-change-ii/description/首先我们可以设计一个缓存
假设到了某一个数字，如果当前数字已经小于了金额，则跳过该数字
如果当前数字大于金额，则存在两种可能
1.放弃该数字，继续往前走
2.挑选一个数字，然后扣减金额，继续在该数字上停留
则可以写出
```js
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) {
result = dfs(amount, pos + 1)
} else {
result = dfs(amount, pos + 1) + dfs(amount - coins, pos)
}
cache.set(flag, result)
return result
}
return dfs(amount, 0)
};
```
那我们现在开始转成动态规划，有两维，一维是金额，一维是硬币，边界时金额为0时则存在一种，同时为了防止边界溢出我们要稍加一点数组
```js
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 = 1
}
for (let index = dp.length - 2; index >= 0; index--) {
for (let mount = 1; mount <= amount; mount++) {
if (mount < coins) {
dp = dp
} else {
dp = dp + dp]
}
}
}
return dp.pop()
};
```
到这里我们可以看到，每一维度仅与上一层和本层金额稍少的位置
那就可以将二维转化成一维，一层一层往上递归，同时又可以发现
我们对硬币从前往后递归和从后往前递归都无所谓
因为每次递归的时候只考虑该层之前的层数存在的可能数
无论硬币数是还是都不会影响答案
那我们可以写出
```js
const change = function (amount, coins) {
const dp = Array(amount + 1).fill(0)
dp = 1
for (const coin of coins) {
for (let mount = 1; mount <= amount; mount++) {
dp = dp + (mount < coin ? 0 : dp)
}
}
return dp.pop()
}
```
将边界略微精简即可得到官解的答案 
页:
[1]