Click: 518. Change Exchange II

Likou: 518. Coin Change II
Title:
Give you an integer array coins representing coins of different denominations, and another integer amount representing the total amount.

Please calculate and return the number of coin combinations that can make up the total amount.Returns 0 if none of the coin combinations make up the total.
Suppose there are infinite coins of each denomination.
The title data guarantees that the result conforms to a 32-bit signed integer.

dp array meaning:
dp[j]: The number of currency combinations that make up the total amount j is dp[j]

Recursive formula:
dp[j] += dp[j - coins[i]];

Initialization:

• First of all, dp[0] = 1 means dp[i] means that the number of currency combinations that make up the total amount of 0 is 1.
• The dp[j] whose subscript is not 0 is initialized to 0, so that the cumulative addition of dp[j - coins[i]] will not affect the real dp[j]

Traversal order:
The complete knapsack problem is also a combination, so it is traversed from small to large, first for items and then nested for knapsack capacity.

Code:

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