0322.coin-change

0322. 硬币兑换

TODO

解法 1 (dynamic-programming-01.js)

动态规划的解法.

1. 构造一个长度为 sum + 1 的数组 (表示完成每个 case 最少需要几个硬币).

2. 将数组全部置为正无穷, 0 的位置置为 0.

3. 遍历整个硬币数组 (意为每增加一种硬币的 case).

4. 在数组中每个小于正无穷 (也就是可以构造出来的 case) 的位置上开始如下计算:

   1. 当前硬币面额 * n (从 1 到总和值大于 sum) + 当前位置值

   2. array[上面的值] 是否大于 构造当前 case 硬币数 + 当前面额硬币的数量

   3. 如果大于, 更新数量值, 表示为更节省的办法.

5. 一直遍历完所有硬币, 查看 array[sum] 位置的情况, 有数字就表示有结果, 是正无穷就表示没有结果.