Skip to Content
CTRL K

Coin Combinations I

Explicación

Sea dp[w]\texttt{dp[w]} igual al número de formas de alcanzar la suma de valores ww. Luego, para algún peso ww, intentemos usar cada moneda. Para dp[w]\texttt{dp[w]}, transicionaremos desde dp[w - coin[i]]\texttt{dp[w - coin[i]]} para todo ii, donde coin[x]\texttt{coin[x]} define el valor de la xx-ésima moneda.

Así, la transición es

dp[w]=∑i=1n(dp[w−coins[i]]) dp[w] = \sum_{i=1}^n{(dp[w - coins[i]])}

Implementación

Complejidad temporal: O(N⋅X)\mathcal{O}(N \cdot X)

#include <iostream>
#include <vector>
 
using std::cout;
 
const int MOD = 1e9 + 7;
 
int main() {
	int n, x;
	std::cin >> n >> x;
	std::vector<int> coins(n), dp(x + 1);
	for (auto &x : coins) { std::cin >> x; }
 
	dp[0] = 1;
	for (int i = 1; i <= x; i++) {
		for (int c : coins) {
			if (i - c >= 0) { (dp[i] += dp[i - c]) %= MOD; }
		}
	}
 
	cout << dp[x] << '\n';
}
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());
		int x = Integer.parseInt(st.nextToken());
		int M = 1000000007;
		st = new StringTokenizer(r.readLine());
		int[] coins = new int[n];
		for (int i = 0; i < n; i++) { coins[i] = Integer.parseInt(st.nextToken()); }
		Arrays.sort(coins);
 
		int[] dp = new int[x + 1];
		dp[0] = 1;
		for (int i = 1; i < dp.length; i++) {
			dp[i] = 0;
			for (int j = 0; j < n; j++) {
				if (coins[j] > i) { break; }
				dp[i] += dp[i - coins[j]];
 
				// hay que usar -= M para pasar en Java en vez de %= M (que
				// funciona en c++) para ahorrar tiempo; esto es lo mismo que dp[i] %
				// m dentro de las restricciones de este problema (dp[i] nunca puede ser
				// > 2*M ya que solo estamos sumando). Esto no sería un problema en
				// contests de USACO ya que USACO da 2x de tiempo para java, pero CSES
				// no. dp[i] %= m;
				if (dp[i] > M) dp[i] -= M;
			}
		}
 
		pw.println(dp[x]);
		pw.close();
	}
}
MOD = 10**9 + 7
 
n, x = map(int, input().split())
coins = list(map(int, input().split()))
 
dp = [0] * (x + 1)
dp[0] = 1
for i in range(1, x + 1):
	for c in coins:
		if i - c >= 0:
			dp[i] = (dp[i] + dp[i - c]) % MOD
 
print(dp[x])
Fundamentos