Change tax for 2

difficulty ： secondary

Give coins of different denominations and a total amount . Write a function to calculate the number of coin combinations that can add up to the total amount . Suppose that there are infinite coins of each denomination .

Example 1:

Input : amount = 5, coins = [1, 2, 5] Output : 4 explain : There are four ways to make up the total 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 explain : Use only face value 2 We can't make up the total amount of 3.

Example 3: Input : amount = 10, coins = [10] Output : 1

Be careful , You can assume ：

0 <= amount ( Total sum ) <= 5000
1 <= coin ( The denomination of the coin ) <= 5000
There are no more kinds of coins 500 Kind of
The result is in line with 32 Bit sign integer

Code

class Solution {
    public int change(int amount, int[] coins) {
         // Recursive expression 
        int[] dp = new int[amount + 1];
        // initialization dp Array , Indicates that the amount is 0 There is only one case , That is to pretend nothing 
        dp[0] = 1;
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];
    }
}