It's the Xinrui Ma

Blog

322. Coin Change – JavaScript Solution

Posted by in LeetCode on

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:

Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Note:
You may assume that you have an infinite number of each kind of coin.

思路:
这个肯定一看就感觉想要用贪心法去做,但是,贪心法做出来是错的。
那么,我们试试DP怎么样?

我们用DP[i]来表示如果总数为I的钱的情况下,使用的最少钱币数, 那么DP[amount]就是我们要求的结果
如果我们能够从DP[0]推出来,DP[1], DP[2] … DP[i]… DP[i + 1], 那就解决了问题

OK, 接下来想想转化公示;
对于coins里面的每一个coin来说,就两种状态,用 还是不用。
不用,那DP[i]就还是DP[i],
用了,那DP[i] = DP[i – coin] + 1

所以我们可以推导出
DP[i] = Math.min(DP[i], DP[i – coin] + 1)

我们对所有的coins都进行这样的遍历,就可以求出来当前的DP[i]的最小值。

我们再对i从0 到amount进行同样的操作,那么我们只要看看最后DP[amount]等于什么就行了

注意最后有可能没有结果 要返回-1, 那么我们就要一个值来标注这个情况下我凑不到这个数,那么什么数你永远凑不到呢?

对于数额为5的面额来说,你最少的硬币数,不可能是6.。。因为最小面额为1,你就是每个都用1毛,那也是5个就完事了。

所以,我们初始化数组的时候,给每个I都赋值I+1,

我们初始条件就很简单喽,DP[0] = 0

Solution: