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 $\text{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 $\text{dp[w - coins[i]]}$ where $\text{coins[i]}$ represents the value of the $i$-th coin. So, for $\text{dp[i]}$, the transition is:

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

1#include <bits/stdc++.h>
2using namespace std;
3using ll = long long;
4using vi = vector<int>;
5#define pb push_back
6#define rsz resize
7#define all(x) begin(x), end(x)
8#define sz(x) (int)(x).size()
9using pi = pair<int,int>;
10#define f first