518. 零钱兑换 II

518. 零钱兑换 II

这里最重要的是将coin循环放在外层

因为放在外层就能保证使用coin的顺序固定

就不会出现3=1+2然后3=2+1的情况

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1);
        dp[0] = 1;
        unordered_set<int> set;
        for(auto coin : coins)
            set.insert(coin);
        for(auto coin : coins)
            for(int i = coin; i <= amount; ++i)
                    dp[i] += dp[i - coin];
        return dp.back();
    }
};