In this problem, we're asked the minimum number of coins of distinct weights needed to achieve some weight, $x$. You can read about the solution to this classical problem in CPH Chapter 7 under "Coin Problem".

Main Idea

For this problem, we'll define $\texttt{dp[w]}$ as the minimum number of coins to achieve some weight, $w$. Then, at some $w$, we can try to use every coin. Using the $i$-th coin represents transitioning from the state $\texttt{dp[w - coins[i]]}$ where $\texttt{coins[i]}$ represents the value of the $i$-th coin. So, for $\texttt{dp[i]}$, the transition is:

Finally, the base case would be $\texttt{dp[0]} = 0$, since it requires $0$ coins to get a sum of $0$.

#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