Yo mismo he luchado con esto, pero con el tiempo he mejorado. Hay muchos otros que pueden dar una mejor respuesta a esta pregunta, pero lo intentaré de todos modos.
Creo que algunas soluciones de arriba hacia abajo se pueden convertir directamente de abajo hacia arriba, pero otras son muy difíciles de convertir y es mejor usar la memorización en tales casos.
Hagamos esto con un ejemplo.
- ¿Puede una computadora generar un número verdaderamente aleatorio?
- Siempre sueño con trabajar en grandes empresas tecnológicas como Google o Facebook, pero mi habilidad con los algoritmos es muy débil. Intento resolver problemas en Google Code Jam y CodeChef, pero solo puedo resolver los fáciles. ¿Qué tengo que hacer?
- ¿Por qué son importantes las estructuras de datos y los algoritmos?
- ¿Qué hago después cuando logré un programa de aprendizaje automático (supervisado) con un 97% de precisión y buen ajuste?
- Algoritmos: ¿Cómo encuentro un elemento en una secuencia que sea más pequeño que mi número en la secuencia, a la izquierda de mi número y a la derecha de todos esos elementos?
Calcularemos el coeficiente binomial. La función recursiva para el coeficiente binomial es:
[matemáticas] {n \ elegir r} = {n-1 \ elegir r-1} + {n-1 \ elegir r} [/ matemáticas]
Supongo que eres capaz de encontrar ecuaciones recursivas pero luchas con la base. Entonces, veamos cómo podemos convertir la definición recursiva anterior en un enfoque ascendente.
Definamos la ecuación anterior como una función f.
[matemáticas] f (n, r) = f (n-1, r-1) + f (n-1, r) [/ matemáticas]
Necesitamos una mesa:
La forma más sencilla de convertir un enfoque de arriba abajo a abajo es creando una tabla y recordando todos los estados. Esto es similar a la memorización pero llenamos la tabla iterativamente en lugar de recursivamente en la memorización.
¿Cuál es el tamaño de la mesa?
Echemos un vistazo a la función nuevamente.
[matemáticas] f (n, r) = f (n-1, r-1) + f (n-1, r) [/ matemáticas]
Nuestra respuesta es el valor f (n, r). Por lo tanto, necesitamos dos dimensiones. El tamaño de las dos dimensiones depende de dónde se encuentre su respuesta. Nuestra respuesta es el valor f (n, r), por lo tanto, necesitamos que la tabla sea de tamaño [matemática] n \ veces r [/ matemática]. Podemos optimizar el espacio y lo haremos más tarde.
Por lo tanto, una matriz bidimensional de tamaño [math] n \ times r [/ math] será suficiente. Ahora, ¿cómo debemos llenar esta matriz? orden mayor de fila, orden mayor de columna? Algo más ?
Cuando miramos nuestra función; para calcular la función [matemáticas] f (i, j) [/ matemáticas], necesitamos valores [matemáticas] f (i-1, j-1) [/ matemáticas] y [matemáticas] f (i-1, j) [/mates]. Por lo tanto, debemos llenarlo de una manera que (i-1, j-1) y (i-1, j) se llene antes de que se llene (i, j). Esto se puede lograr llenando la matriz en orden mayor de fila u orden mayor de columna.
Ahora solo necesitamos dos bucles anidados para llenar la matriz en orden de fila mayor o columna mayor. También necesitamos completar los valores iniciales, es decir, la fila 0 y la columna 0.
int dp[n][r];
for(int i=1;i<n;i++)
{
for(int j=1;j<r;j++)
{
dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
}
}
Ya casi hemos terminado. Prometimos que optimizaremos el espacio. Tenga en cuenta que cuando llenamos una fila, solo necesitamos una fila anterior y no todas las filas anteriores. Por lo tanto, necesitamos un espacio auxiliar O (r) y podemos barajar entre las filas actuales y anteriores.
Solo cambio en el código:
int dp[2][r];
for(int i=1;i<n;i++)
{
for(int j=1;j<r;j++)
{
dp[i%2][j] = dp[(i-1)%2][j-1] + dp[(i-1)%2][j];
}
}
Espero que ayude.