Problema de programación dinámica “Two Sets II”
Estoy tratando de resolver
Dice lo siguiente:
Tu tarea es contar el número de maneras en que los números 1, 2,…, n se pueden dividir en dos conjuntos de igual suma.
Por ejemplo, si n=7, hay cuatro soluciones:
{1,3,4,6} y {2,5,7}
{1,2,5,6} y {3,4,7}
{1,2,4,7} y {3,5,6}
{1,6,7} y {2,3,4,5}
Esto es lo que tengo hasta ahora:
int n;
cin >> n;
int maxSum = n * (n + 1) / 2;
if (maxSum % 2 != 0) {
cout << 0 << endl;
return 0;
}
maxSum /= 2;
vector<vector<long>> dp(n+1, vector<long>(maxSum+1));
dp[0][0] = 1;
for (int currentNumIncluded = 1; currentNumIncluded <= n; ++currentNumIncluded) {
for (int currentTargetSum = 0; currentTargetSum <= maxSum; ++currentTargetSum) {
dp[currentNumIncluded][currentTargetSum] = dp[currentNumIncluded-1][currentTargetSum];
int remainder = currentTargetSum – currentNumIncluded;
if (remainder >= 0) {
dp[currentNumIncluded][currentTargetSum] += dp[currentNumIncluded-1][remainder];
dp[currentNumIncluded][currentTargetSum] %= 1000000007;
}
}
}
cout << dp[n][maxSum]/2 << endl;
Uso DP simple para resolverlo. Sin embargo, no pasa 5 de 26 casos de prueba. Busqué y resulta que si imprimimos dp[n-1][maxSum] en lugar de dp[n][maxSum]/2, todo funciona. ¿Podría alguien explicarme esto?
davy.ai
Parece que el problema puede estar relacionado con el hecho de que divides
dp[n][maxSum]por 2 al final, mientras se calcula el resultado. Dividir por 2 asume que cada solución se cuenta dos veces, una para cada uno de los dos conjuntos de suma igual, pero esto puede no ser siempre el caso.Por ejemplo, si
n=4, la única solución es{1,4}y{2,3}, que es contada una vez por tu algoritmo, pero solo pertenece a un conjunto de suma igual. Por lo tanto, dividir por 2 llevaría a un resultado incorrecto.Imprimir
dp[n-1][maxSum]en lugar dedp[n][maxSum]/2podría funcionar porque no asume que cada solución se cuenta dos veces. En otras palabras, cuenta cada solución solo una vez, independientemente de a qué conjunto de los dos pertenece.Sin embargo, esto es solo una suposición sin conocer los casos de prueba exactos que fallan y el resultado esperado para esos casos. También es posible que el problema esté relacionado con una parte diferente de tu código o algoritmo.