CSES - Minimizing Coins

Explanation

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".

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$.

Implementation

Time Complexity: $\mathcal O(N\cdot X)$

Copy
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll dp[1000001];

const int MOD = 1e9 + 7;

int main() {
	int n, x;

Copy
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class MinCoins {
	public static int MAX = (int)10e6 + 2;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

Copy
INF = 1000000000  # Using float('inf') results in a TLE

n, x = map(int, input().split())
c = list(map(int, input().split()))

dp = [INF] * (x + 1)
dp[0] = 0  # Base case: 0 coins are needed for a sum of 0

for coin in c:
	for i in range(x - coin + 1):