LeetCode: 518. Coin Change 2

发表于 | 分类于

题目描述

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

Example 1:

1
2
3
4
5
6
7
Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

Example 2:

1
2
3
Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.

Example 3:

1
Input: amount = 10, coins = [10]

这题很明显可以用DP来做，但是要注意的是，题目要求给出组合的数，而不是要给所有结果的排列。

为了在DP中实现这种类似于组合的方法，我们想象一下把所有的结果进行从小到大的排序。如果我们使用DP得到的结果能保证有序性，那么我们得到的一定就是一个排列。（比如在算amount为5的时候，先有1 1 1 1 1，然后1 1 1 2， 1 2 2，5）

为了实现这种有序性，我们可以在dp的for循环中，把coins的index作为外层的循环，言下之意就是先仅仅使用1，然后再在现有的基础上尝试使用2（但是一旦使用2了，就不能再使用1了），最后再使用5。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount+1);
        if (amount == 0) {
            return 1;
        }
        if (coins.size() == 0) {
            return 0;
        }

        for (int j = 0; j < coins.size(); j++) {
            for (int i = 0; i < dp.size(); i++) {
                if (i-coins[j] == 0) {
                    dp[i] += 1;
                }
                if (i-coins[j] >= 0) {
                    dp[i] += (dp[i-coins[j]]);
                }
            }
        }
        return dp[dp.size()-1];
    }
};