Description Link to heading

518.coin-change-ii

Solution Link to heading

This problem is still a unbounded-knapsack-problem. What this problem need to solve is combination rather than combination.

If we want to get the number of combination, we should traverse items first, than traverse volume. But if you want to get the number of permutation, you should traverse volume first, than traverse items.

For example, assume that nums = {1, 2}, target = 3

dp[0] = 1;
for (int i = 0; i < 2; i++) {
    for (int j = nums[i]; j <= target; j++)
        dp[j] = dp[j] + dp[j - nums[i]];
}

dp[3] == 2, combnations: {1, 1, 1}, {1, 2}.

dp[0] = 1;
for (int j = 0; j <= target; j++) {
    for (int i = 0; i < 2; i++) {
        if (j >= nums[i])
            dp[j] = dp[j] + dp[j - nums[i]];
    }
}

dp[3] = 3, permutations: {1, 1, 1}, {1, 2}, {2, 1}.

Code Link to heading 

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