Sí, hay una forma y en este caso podes usar lo que se llama programación dinámica.
Un algoritmo dinámico busca la resolución la mediante la combinación de subproblemas del mismo tipo. A diferencia de divide et impera, pediremos que los subproblemas se solapen.
Que los subproblemas se solapen significa que el problema lo dividimos en subproblemas que son reutilizados varias veces, o que estos subproblemas comparten subsubproblemas.
Un ejemplo típico es Fibonacci, donde al resolver fib(50) recursivamente, se termina recomputando muchísimas veces fib(3) por ej.
Se divide en top-down y bottom-up, te recomiendo que busques programación dinámica en sí y aprendas sobre ella.
Primero aprendé a como calcular la factorial de un número sin recalcularlo tantas veces utilizando programación dinámica por supuesto.
Y te dejo esto aca:
#include <stdio.h>
#include <stdlib.h>
#define MAXN 50
#define MAXK 50
int comb(int n, int k) {
static int table[MAXN][MAXK] = { 0 };
if (k == 0 || n == k)
return 1;
if (table[n][k] != 0)
return table[n][k];
table[n][k] = comb(n - 1, k) + comb(n - 1, k - 1);
return table[n][k];
}
int comb_(int n, int k) {
int table[n+1][k+1];
int i, j;
for (i = 0; i <= n; i++)
table[i][0] = 1;
for (i = 0; i <= n; i++)
table[i][i] = 1;
for (i = 0; i <= n; i++)
for (j = 1; j <= k && j < i; j++)
table[i][j] = table[i - 1][j - 1] + table[i - 1][j];
return table[n][k];
}
int main(void) {
printf("%d", comb_(10, 9));
return 0;
}El primero es TOP-DOWN y el segundo BOTTOM-UP, los dos son eficientes porque no calculan varias veces lo mismo.
Si implementamos este código:
int fib(int n)
{
if ( n <= 1 )
return n;
return fib(n-1) + fib(n-2);
}Pasaría esto:
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ / \ / \
fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
/ \
fib(1) fib(0)
La fib(2) y fib(3) se recalcula varias veces, cuando ponemos un numero más grande la cosa empeora todavía más.
De todos modos no sé ni en qué lenguaje lo estás programando.
Saludos.
