Permítame recordarle la hermosa propiedad de los coeficientes binomiales que nos permite resolver este problema utilizando la programación dinámica:
[matemáticas] \ binom {n} {k} = \ frac {n} {k} \ binom {n-1} {k-1} [/ matemáticas]
Implementemos una solución recursiva sencilla (C ++ como el código pseuso):
- ¿Cómo calcula Google la distancia entre dos lugares en Google Maps?
- Cuando reviso algo en Google, muestra una lista de sitios web. Pero, ¿cómo selecciona lo mejor de 1000 sitios web? ¿Hay algún algoritmo?
- ¿Alguien ha probado algún algoritmo de aprendizaje automático en diseño o verificación de hardware?
- Quiero aprender más sobre algoritmos, pero no sé por dónde empezar. ¿Me puede dar algunas instrucciones o consejos? Gracias.
- Si [matemática] f (n) [/ matemática] [matemática] \ en O (n) [/ matemática] y [matemática] g (n) \ en O (n) [/ matemática], es [matemática] f ( g (n)) \ en O (n ^ 2)? [/ matemáticas]
int binom (int n, int k)
{
afirmar (n> = k);
si (k == 0) devuelve 1;
binomio de retorno (n-1, k-1) * n / k;
}
A pesar de ser muy simple, es sorprendentemente eficiente. El árbol de recursión no es ramificado, solo n llamadas recursivas consecutivas, lo que nos da complejidad O (n) tiempo y O (n) espacio (pila de llamadas).
Ahora vamos a agregar memorización usando el mapa hash. Tenga en cuenta que esto no tiene mucho sentido para este problema en particular , pero es muy útil para problemas en los que una función recursiva se llama a sí misma varias veces con diferentes valores de argumento. En tales casos, la memorización generalmente reduce la complejidad del tiempo de tiempo exponencial a tiempo polinómico. Pero hagámoslo de todos modos:
par de estructura
{
int n;
int k;
Par (int N, int K) {n = N; k = K;}
};
HashMap dp;
int binom (int n, int k)
{
afirmar (n> = k);
si (k == 0) devuelve 1;
Par p = Par (n, k);
if (dp.hasKey (p)) devuelve dp.get (p);
int resultado = binom (n-1, k-1) * n / k;
dp.set (p, resultado);
resultado de retorno;
}
Ahora deshazte de la recursividad:
int binom (int n, int k)
{
HashMap dp;
/ * llenar los casos base (k == 0) * /
para (int i = 0; i <= n; i ++)
dp.set (Par (i, 0), 1);
/ *
Ahora llena el resto
En cada iteración garantizamos que (i-1, j-1)
binom ya ha sido calculado
* /
para (int i = 1; i <= n; i ++)
para (int j = 1; j <= k; j ++)
{
int prev = dp.get (Par (i-1, j-1));
dp.set (Par (i, j), anterior * i / j);
}
return dp.get (Par (n, k));
}
¿No crees que un mapa hash es demasiado aquí? Sustitúyalo por una matriz 2d y obtenga un código más elegante:
int binom (int n, int k)
{
int dp [n + 1] [k + 1];
/ * llenar los casos base (k == 0) * /
para (int i = 0; i <= n; i ++)
dp [i] [0] = 1;
para (int i = 1; i <= n; i ++)
para (int j = 1; j <= k; j ++)
dp [i] [j] = dp [i-1] [j-1] * i / j;
devuelve dp [n] [k];
}
Puede observar fácilmente el hecho de que para calcular dp[n][k] solo necesitamos el elemento dp[n-1][k-1] , que en su caso necesita dp[n-2][k-2] precalculado y así sucesivamente hasta alcanzar el caso base dp[nk][0] = 1 . Siga adelante y use la observación:
int binom (int n, int k)
{
afirmar (n> = k);
/ * Mantener dp [i] [j] en el resultado * /
int resultado = 1; // dp [nk] [0]
para (int j = 1; j <= k; j ++)
resultado = resultado * (n-k + j) / j;
resultado de retorno;
}
Súper genial y elegante solución de competencia O (n) tiempo y O (1) espacio.
* Se recomienda encarecidamente corregir errores.
