https://practice.geeksforgeeks.org/problems/coin-change2448/1

class Solution {
  long long dp[1005][1005];

public:
  long long int count(int S[], int m, int n) {
    memset(dp, -1, sizeof(dp));

    for (int i = 0; i <= m; i++) {
      dp[i][0] = 1;
    }

    for (int j = 1; j <= n; j++) {
      dp[0][j] = 0;
    }

    for (int i = 1; i <= m; i++) {
      for (int j = 1; j <= n; j++) {
        if (S[i - 1] <= j) {
          dp[i][j] = dp[i - 1][j] + dp[i][j - S[i - 1]];
        } else {
          dp[i][j] = dp[i - 1][j];
        }
      }
    }

    return dp[m][n];
  }
};