¿Sigue siendo necesario convertir una solución dp memorable en una iterativa?

Estás casi en lo correcto.

Hay 4 cosas en términos simples:

1. Iteración – ej .: for loop
2. Recursión – ej: una función que se llama a sí misma
1. Aquí, el tiempo de ejecución es recordar argumentos de función para usted para cada llamada a sí mismo, por lo que está utilizando memoria
3. Memorización
1. Principalmente recordando cálculos pasados ​​y reutilizándolos en lugar de volver a calcularlos
1. Para la memorización, las personas usan la matriz memo [] para recordar
4. Programación dinámica (DP)
1. Iteración / recursión para una / todas las permutaciones o a / todas las combinaciones u otras +/- Memoración
1. Para la memorización mientras se realiza DP, las personas usan la matriz dp [] para recordar, esta es la matriz memo [] en la memorización.
2. Algunos confunden que dp [] array se debe a la programación dinámica, pero dp [] array es Memoization.

Como podemos ver:

• ¿Cuál es la diferencia entre [matemáticas] 2 ^ {n ^ {o (1)}} [/ matemáticas] y [matemáticas] 2 ^ {O (n ^ e)} [/ matemáticas] (para algunos e <1)?
• ¿Cuál ha sido la experiencia general con el producto de optimización creativa dinámica (DCO) de Tumri?
• ¿Cuáles son los mejores sitios web con problemas de práctica de algoritmos?
• ¿Qué otras formas fundamentales de compresión de datos, pero la omisión de patrones irrelevantes y la explotación de patrones repetitivos existen?
• Conozco la implementación básica de diferentes estructuras de datos como árboles, gráficos, colas y muchos más para inserción, eliminación, recorrido. Ahora, ¿cómo procedo a construir un sistema operativo?

1. DP puede ser tanto iterativo como recursivo, por el mismo problema.
2. Suponiendo que DP tiene subproblemas superpuestos: entonces DP siempre usa Memoization para guardar soluciones a esos subproblemas, de lo contrario es ineficiente.

La diferencia:

1. DP recursivo
1. Debido a la naturaleza recursiva, es simple escribir
1. Todo lo que tienes que encontrar es:
2. una fórmula recursiva y
3. Una condición básica que sale de la recursión
2. Debido a la naturaleza recursiva, recuerda las llamadas a funciones, por lo que es muy probable que se acumule desbordamiento, especialmente en nuestros sistemas locales de memoria pequeña.
1. Para ampliar la pila en MS Visual C ++, las personas usan a continuación:
2. # comentario de pragma (enlazador, “/ STACK: 36777216”)
3. El número 36777216 aquí se puede cambiar según la necesidad.
4. Este stack over flow puede ocurrir en sitios web de programación competitivos donde existe una gran memoria, pero es muy raro.
2. DP iterativo
1. Generalmente no es fácil escribir
2. Solo es fácil escribir después de pasar mucho tiempo observando varios patrones del problema o mediante DP recursiva
3. Como no se llama a sí mismo de forma recursiva, no tiene llamadas a funciones de recuerdo, por lo que no hay problemas con el desbordamiento de la pila, por lo que es bueno iterar.

Resumen:

1. Siempre escribiría un DP recursivo con memorización, ya que es una respuesta instantánea, una función recursiva y una condición básica para romper la recursividad.
2. Si hay un desbordamiento / error, entonces sé que se debe al mal uso de los argumentos de la función:
1. Reduce el tamaño de los argumentos de la función
1. Si los argumentos de la función tienen long long o long, entonces, verificaría y cambiaría a un tipo de tamaño menor como short, o unsigned char (que tal vez pasé por alto de alguna manera para empezar)
2. Esto pasa casi siempre.
2. Reduce el número de argumentos de función
1. si a) no es el problema, entonces habría tenido más parámetros en la llamada de función que los requeridos
2. Ejemplo: si tengo 5 argumentos de función, puede que algunos sean constantes, por lo que los hago variables globales (o variables de clase estáticas si se usa una clase), entonces con argumentos reducidos, puede haber solo 2 argumentos, siempre pasa
3. Todavía no he visto que solo el DP iterativo pasa, pero el DP recursivo falla, pero puede ser posible debido a la naturaleza recursiva como se describió anteriormente.
4. Después de los 2 puntos de optimización anteriores, casi siempre paso solo en DP recursivo.
5. Solo por el conocimiento de Iterative DP, algunas veces lo codifico en iterativo. También porque a algunos famosos se les da tanto recursivos como iterativos.
6. Después de resolver algunos problemas, no encuentro mucha diferencia entre ambos, pero obtengo la lógica utilizando la comprensión recursiva principalmente, y luego la cambio de forma iterativa.
7. Finalmente, el DP iterativo se ve más rápido por las razones obvias descritas anteriormente, pero el DP recursivo es mucho más simple de codificar.

Dado que los problemas de DP son difíciles de resolver, cualquier DP está bien siempre que resuelva el problema, cualquiera estaría bien con cualquiera de las soluciones de DP: iterativa / recursiva.

Espero que haya ayudado.