[InterviewBit] Coin Sum Infinite

Coin Sum Infinite

  • Time :
  • Space :
1
2
3
4
5
6
7
8
9
10
11
12
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];
}

Author: Song Hayoung
Link: https://songhayoung.github.io/2022/10/12/PS/interviewbit/coin-sum-infinite/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.