Coin Sum Infinite

• Time : $O(AB)$
• Space : $O(B)$

c++

int Solution::coinchange2(vector<int> &A, int B) {
    vector<long long> dp(B + 1);
    long long mod = 1000007;
    dp[0] = 1;
    for(auto a : A) {
        for(int i = 0; i <= B - a; i++) {
            if(dp[i]) dp[i+a] = (dp[i+a] + dp[i]) % mod;
        }
    }
    return dp[B];
}