In this problem, we are asked the number of ways to achieve some value, $x$, using $n$ coins of distinct values where the order of coins does not matter. This is known as the "Unordered Coin Change" problem, which you can read about in CPH Chapter 7 under "Counting the Number of Solutions".

Main Idea

To solve this problem, let $\texttt{dp[w]}$ equal the number of ways to achieve the sum of values, $w$. Then, for some weight $w$, let's try to use each coin. For $\texttt{dp[w]}$, we'll transition from $\texttt{dp[w - coin[i]]}$ for all $i$, where $\texttt{coin[x]}$ defines the value of the $x$-th coin.

So, the transitions are:

Example Code

Copy
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pi = pair<int, int>;
#define f first

Copy
import java.io.*;
import java.util.*;

public class CountingCoins1 {
	static BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter pw = new PrintWriter(System.out);

	public static void main(String[] args) throws IOException {
		StringTokenizer st = new StringTokenizer(r.readLine());
		int n = Integer.parseInt(st.nextToken());