The Coin Change Problem

c++

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);
}