> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/dynamic_programming_i/bei-bao-wen-ti/coin-change-2.md).

# Coin Change 2

<https://leetcode.com/problems/coin-change-2/description/>

> 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.
>
> Note: You can assume that
>
> 0 <= amount <= 5000
>
> 1 <= coin <= 5000
>
> the number of coins is less than 500
>
> the answer is guaranteed to fit into signed 32-bit integer
>
> Example 1:
>
> 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:
>
> Input: amount = 3, coins = \[2]
>
> Output: 0
>
> Explanation: the amount of 3 cannot be made up just with coins of 2.
>
> Example 3:
>
> Input: amount = 10, coins = \[10]
>
> Output: 1

## Thoughts

和coin change I一样是完全背包问题, 不同的是要求返回的不再是最少次数, 而是总共次数, 因此用+=.

## Code

```
class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> f(amount + 1, 0);
        f[0] = 1;
        for (int i = 0; i < coins.size(); ++i) {
            for (int j = coins[i]; j <= amount; ++j) {
                f[j] += f[j - coins[i]];  
            }
        }

        return f[amount]; 
    }
};
```

```
class Solution {
    public int change(int amount, int[] coins) {
        int[] f = new int[amount + 1];
        f[0] = 1;

        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                f[j] += f[j - coins[i]];
            }
        }

        return f[amount];
    }
}
```

## Analysis

时间复杂度O(MN).