Requirements:

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:

Input: Amount =5, Coins = [1, 2, 5] Input: Amount =5, Coins = [1, 2, 5] There are four ways to make a total amount: 5=5 5=2+2+1 5=2+1+1 5=1+1+1+1 Amount = 3, coins = [2] Input: Amount = 10, Coins = [10] Output: 1Copy the code

Ideas:

  1. Status: two, backpack capacity and optional items.
  2. Choice: Pack in backpack or not pack in backpack. Coins [I]=dp[I][j]= DP [i-1][j] If the ith item is loaded into the backpack, DP [I][j]= DP [I][H-coins [I-1]] Coins [i-1] is the i-th coin. So dp[I][j] is really the sum of the two choices.
  3. The definition of dp array: dp[I][j] means that if only the first I items are used, when the backpack capacity is J, there are dp[I][j] methods to fill the backpack.
  4. base case:dp[0][…] =0, dp[…] [0] = 1; You can’t make any coins without using coins. If the target amount is 0, there must be only one choice, nothing.
  5. Return value: dp[N][amount], where N is the size of the Coins array
Template:int dp[N][amount+1]
dp[0] [...]. =0dp[...] [0] =1

for i in [1. N]:for j in [1. Amount]: put item I into backpack not put item I into backpackreturn dp[N][amount]
Copy the code

Code:

class Solution {
    public int change(int amount, int[] coins) {
        int n = coins.length;
        int[][] dp = new int[n+1][amount+1];
        for (int i = 0; i < n+1; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i < n+1; i++) {
            for (int j = 1; j < amount+1; j++) {
                if (j-coins[i-1] > =0) {// The size of the backpack will fit
                    dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]];
                } else {
                    dp[i][j] = dp[i-1][j]; }}}returndp[n][amount]; }}Copy the code