¿Cuáles son algunos conceptos que debo saber antes de aprender programación dinámica? La tecnología cambia la vida futura

¿Cuáles son algunos conceptos que debo saber antes de aprender programación dinámica?

Recursión : pienso en la programación dinámica como Recursion + Memoization. Verá que los problemas de programación dinámica tienen una subestructura óptima. Lo que esto significa es que una solución para [math] f (n) [/ math] es óptima si y solo si una solución para [math] f (nk) [/ math] es óptima. Entonces, todo lo que necesitas hacer es pensar de forma recursiva. Defina la propiedad recursiva y simplemente amplíela.
Tomemos un ejemplo: la mayor secuencia creciente
Por lo tanto, se le proporciona una matriz y desea encontrar la subsecuencia de mayor crecimiento de esta matriz. Como hay subsecuencias [matemáticas] 2 ^ n [/ matemáticas], el enfoque ingenuo no funcionará. Intentemos encontrar su propiedad recursiva. Deje que [math] f (i) [/ math] sea la subsecuencia de mayor crecimiento de [math] a_ {1}, .. a_ {i} [/ math] que tiene [math] a_i [/ math] como último elemento . Es fácil ver que es para algunos [matemática] k [/ matemática], si [matemática] a_k <a_i [/ matemática] entonces [matemática] f (i) = f (k) + 1 [/ matemática]. Si iteramos sobre todas [matemáticas] k [/ matemáticas], de [matemáticas] 1 [/ matemáticas] a [matemáticas] i-1 [/ matemáticas] y verificamos cada valor y actualizamos [matemáticas] f (i) [/ matemáticas ] para ser el máximo de todas [matemáticas] f (k) + 1 [/ matemáticas], habremos terminado. Eso es todo, tenemos nuestra propiedad recursiva. Todo lo que queda por hacer ahora es codificarlo. Lo cual será bastante fácil de hacer si sabes recurrencia. Si no conoce la memorización, lea sobre ella. Aquí hay un código de muestra que lo hace:
int mem[1000] = {0}; mem[0] = 1; int lis(int ar[], int n){ if(mem[n-1] == 0 ){ mem[n-1] = 1; for(int i=0; i<n-1; i++){ if(ar[i] < ar[n-1]) mem[n-1] = max(mem[n-1], lis(i)+1); } } return mem[n-1]; }

int mem[1000] = {0}; mem[0] = 1; int lis(int ar[], int n){ if(mem[n-1] == 0 ){ mem[n-1] = 1; for(int i=0; i<n-1; i++){ if(ar[i] < ar[n-1]) mem[n-1] = max(mem[n-1], lis(i)+1); } } return mem[n-1]; }
Pensamiento de abajo hacia arriba . Aunque la recursividad + la memorización es buena, requieren espacio de pila adicional y, por lo tanto, construir la solución desde abajo siempre es mejor (aunque no más fácil). Lo que esto significa es que, use [math] f (1), f (2), .. f (k) [/ math] para encontrar una solución a [math] f (n) [/ math]. Calcule esos [math] f (i) [/ math] primero y luego calcule [math] f (n) [/ math] usándolos. Esto hará que la solución sea iterativa y, por lo tanto, será más rápida que la de memorización. La versión de memorización anterior se puede traducir a un enfoque ascendente muy fácilmente:
int lis(int ar[], int n){ int *mem = new int[n]; for(int i=0; i<n; i++){ mem[i] = 1; for(int j=0; j<i; j++){ if(ar[j] < ar[i]) mem[i] = max(mem[i], mem[j] +1); } } return mem[n-1]; }
Práctica: La práctica te hará mejor. Encuentre preguntas e intente resolverlas por su cuenta.