[Hacker Rank] The Coin Change Problem

The Coin Change Problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
long long dp[251][51];
long long helper(long long cur, long long n, vector<long>& A, int last) {
if(cur == n) return 1;
if(cur > n) return 0;
if(dp[cur][last] != -1) return dp[cur][last];
dp[cur][last] = 0;
for(int i = last; i < A.size(); i++) {
dp[cur][last] += helper(cur + A[i], n, A, i);
}
return dp[cur][last];
}
long getWays(int n, vector<long> c) {
memset(dp, -1, sizeof dp);
return helper(0, n, c, 0);
}
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/05/29/PS/HackerRank/the-coin-change-problem/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.