Skip to Content
CTRL K

Coin Combinations II

Editorial no oficial (C++) 

La diferencia clave entre este problema y Coin Combinations I  es que ahora intentamos hallar el número de formas ordenadas de sumar las monedas hasta xx. Esto significa que si tuviéramos monedas {1,3,5}\{1, 3, 5\} y x=4x=4, sumar 1+31 + 3 se trata como la misma “forma” que 3+13 + 1.

Solución

Dejaremos que dp[w]\texttt{dp}[w] sea igual al número de formas ordenadas de sumar las monedas hasta ww. En el problema anterior, probábamos cada moneda para cada ww posible. Aquí haremos lo inverso, recorriendo todos los ww posibles (0≤w≤x0\leq w \leq x) para cada moneda ii mientras actualizamos dp\texttt{dp} de la siguiente forma:

dp[w]:=dp[w]+dp[w−coins[i]] \texttt{dp}[w] := \texttt{dp}[w] + \texttt{dp}[w-\texttt{coins}[i]]

Esto esencialmente implica intercambiar el orden de los bucles anidados del problema anterior. Como ahora recorremos las monedas antes que los pesos, solo pasamos una vez por el conjunto de monedas, así que es imposible crear dos combinaciones con el mismo conjunto de monedas ordenado de forma distinta.

Implementación

Complejidad temporal: O(n⋅x)\mathcal{O}(n \cdot x)

#include <bits/stdc++.h>
using namespace std;
 
const int MOD = 1e9 + 7;
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	int n, x;
	cin >> n >> x;
 
	vector<int> coins(n);
	for (int i = 0; i < n; i++) { cin >> coins[i]; }
 
	vector<long long> dp(x + 1);
	dp[0] = 1;
 
	// Procesar cada moneda una vez para que cada combinación se cuente solo una vez
	// (El orden de las monedas no importa aquí)
	for (int coin : coins) {
		for (int sum = coin; sum <= x; sum++) {
			dp[sum] += dp[sum - coin];
			dp[sum] %= MOD;
		}
	}
 
	cout << dp[x] << '\n';
}
import java.util.*;
 
public class CoinCombinations2 {
	static final int MOD = 1000000007;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int x = sc.nextInt();
 
		int[] coins = new int[n];
		for (int i = 0; i < n; i++) { coins[i] = sc.nextInt(); }
 
		// dp[w] = el número de formas ordenadas de sumar monedas hasta w
		int[] dp = new int[x + 1];
		dp[0] = 1;
		for (int i = 0; i < n; i++) {       // recorrer monedas
			for (int w = 0; w <= x; w++) {  // recorrer sumas
				if (w - coins[i] >= 0) {    // evitar casos fuera de rango
					dp[w] = (dp[w] + dp[w - coins[i]]) % MOD;
				}
			}
		}
		System.out.println(dp[x]);
	}
}
import sys
 
MOD = 10**9 + 7
 
input = sys.stdin.readline  # Entrada más rápida. Usar input() normal da TLE.
 
n, x = map(int, input().split())
coins = list(map(int, input().split()))
 
combinations = [0] * (x + 1)
combinations[0] = 1
 
for coin in coins:
	for i in range(len(combinations)):
		if i - coin >= 0:
			combinations[i] += combinations[i - coin]
			combinations[i] %= MOD
 
print(combinations[x])
Fundamentos