Coin change problem (Editorial)

Let f(k, n) denote the number of ways to make the sum $n$ using the first $k$ denominations of coins. This number is equal to the sum of two quantities:

• the number of ways to make the sum $n$ using the first (k - 1) denominations (i.e., without using the $k$-th denomination), and

• the number of ways to make the sum (n - a_k) using all $k$ denominations.

Thus, we have the following relationship:

Initially, we set f(0, 0) = 1, f(0, n) = 0 for n > 0.

Example

Let's consider the second example. Here, the sum n = 10 and there are k = 4 denominations. The last denomination has a value of a_k = 6. According to the relationship, we have:

The sum of $10$ can be made using the first three denominations \{2, 5, 3\} in $4$ ways:

The sum of $4$ can be made using all four denominations \{2, 5, 3, 6\} in $1$ way:

Algorithm realization

Declare the arrays.

long long dp[51][251];
int a[51];

The value of f(k, n) will be stored in dp[k][n].

long long f(int k, int n)
{
  if (k == 0 && n == 0) return 1;
  if (k == 0 || n < 0) return 0;
  if (dp[k][n] != -1) return dp[k][n];
  return dp[k][n] = f(k - 1, n) + f(k, n - a[k]);
}

The main part of the program. Read the input data.

memset(dp, -1, sizeof(dp));
scanf("%d %d", &n, &m);
for (i = 1; i <= m; i++)
  scanf("%d", &a[i]);

Print the required number of ways.

printf("%lld\n", f(m, n));

Python realization

The value of f(k, n) will be stored in dp[k][n].

def f(k, n):
  if k == 0 and n == 0:
    return 1
  if k == 0 or n < 0:
    return 0
  if dp[k][n] != -1:
    return dp[k][n]
  dp[k][n] = f(k - 1, n) + f(k, n - a[k])
  return dp[k][n]

The main part of the program. Read the input data.

n, m = map(int, input().split())
a = [0] + list(map(int, input().split()))
dp = [[-1 for _ in range(n + 1)] for _ in range(m + 1)]

Print the required number of ways.

print(f(m, n))