[LeetCode] 518. Coin Change 2

https://leetcode.com/problems/coin-change-2/?tab=Description

Solution:
This is one of the classical questions for dynamic programming. And it belongs to the complete 01 knapsack problem. Let's suppose dp[i][j] represents the number of ways to make up amount of j with 1 to ith coins. Then when we move onto the next coin, we have to make choice. If the denomination of the next coin larger than j, then we cannot use it; if smaller, we can use it. Thus, the transition formula is:
                       dp[i+1][j] = dp[i][j] + dp[i+1][j-v[i+1]]
The first term means the way without using the (i+1)th coin; and the second one means the way with using the (i+1)th coin. This equation can be further simplified into an one-dimensional vector,
                      dp[j] = dp[j] + dp[j-v[i+1]]
                  or, dp[j] += dp[j-v[i+1]]
 See code below.

Code:

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