Coin Change

// Coin Change
// n = 4, m = 3, S[] = {1, 2, 3} => 4 : {1, 1, 1, 1}, {1, 1, 2}, {2, 2}, {1, 3}
// https://www.geeksforgeeks.org/coin-change-dp-7/
// dp[i][j] = dp[i][j - 1] + dp[i - S[j]][j] // nr de moduri daca nu includem coin - ul j + nr de moduri daca includem coin - ul j

class Solution {
    public:
        long long int count(int S[], int m, int n) {
            vector < long long int > dp(n + 1);
            dp[0] = 1;
            for(int i = 0; i < m; ++i)
                for(int j = S[i]; j <= n; ++j)
                    dp[j] += dp[j - S[i]];
            return dp[n];
        }
};