The article directories

      • 518. Change II
        • Topic describes
        • thinking
        • Dynamic programming code

518. Change II

Topic describes

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

Example 1: Input: Amount =5, Coins = [1, 2, 5] Output: 4 Description: There are four ways to obtain the total amount: 5=5 5=2+2+1 5=2+1+1 5=1+1+1+1+1

Example 2: Input: Amount = 3, Coins = [2] Output: 0

Example 3: Input: Amount = 10, Coins = [10] Output: 1

Note: 0 <= amount <= 5000 1 <= coin <= 5000 No more than 500 coin types result is a 32-bit signed integer

thinking

There’s an infinite number of them, not counting the order, which is a complete knapsack problem.

But in this case and pure complete backpack is not the same, pure complete backpack is whether the total amount, and in this case is the number of total amount!

First, dp[0] must be 1. Dp [0] = 1 is the basis of the recursive formula. From the meaning of DP [I], it means that the number of currency combinations that make up the total amount of 0 is 1. Second, dp[j] with a non-zero subscript is initialized to 0, so that dp[j-coins [I]] will not affect real DP [j].

Dynamic programming code

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp=new int[amount+1];
        dp[0]=1;
        for(int i=0; i<coins.length; i++){for(int j=coins[i]; j<=amount; j++) dp[j]=dp[j]+dp[j-coins[i]]; }returndp[amount]; }}Copy the code