组合数

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。计算并返回可以凑成总金额的硬币组合数。

输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int>dp(amount + 1);
        dp[0] = 1;
        //求组合数 coin放外面
        for(int coin : coins) {
            for(int i = 0; i <= amount; i++) {
                if(i >= coin) {
                    dp[i] += dp[i - coin];
                }
            }
        }
        return dp[amount];
    }
};

• ← Previous Post
• Next Post →