La programación dinámica es una técnica que divide los problemas en subproblemas y guarda el resultado para propósitos futuros, de modo que no necesitemos calcular el resultado nuevamente. Los subproblemas se optimizan para optimizar la solución general, lo que se conoce como propiedad de subestructura óptima. El uso principal de la programación dinámica es resolver problemas de optimización. Aquí, los problemas de optimización significan cuando intentamos encontrar la solución mínima o máxima de un problema. La programación dinámica garantiza encontrar la solución óptima de un problema si la solución existe.

La definición de programación dinámica dice que es una técnica para resolver un problema complejo dividiéndolo primero en una colección de subproblemas más simples, resolviendo cada subproblema solo una vez y luego almacenando sus soluciones para evitar cálculos repetitivos.

Entendamos este enfoque a través de un ejemplo.

Considere un ejemplo de la serie de Fibonacci. La siguiente serie es la serie de Fibonacci:

que significa xd

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ,…

Los números de la serie anterior no se calculan al azar. Matemáticamente, podríamos escribir cada uno de los términos usando la siguiente fórmula:

F(n) = F(n-1) + F(n-2),

Con los valores base F(0) = 0 y F(1) = 1. Para calcular los otros números, seguimos la relación anterior. Por ejemplo, F(2) es la suma f(0) y f(1), que es igual a 1.

¿Cómo podemos calcular F(20)?

El término F(20) se calculará utilizando la enésima fórmula de la serie de Fibonacci. La siguiente figura muestra cómo se calcula F(20).

cómo inyectar una clase abstracta simulada

Como podemos observar en la figura anterior, F (20) se calcula como la suma de F (19) y F (18). En el enfoque de programación dinámica, intentamos dividir el problema en subproblemas similares. Estamos siguiendo este enfoque en el caso anterior donde F(20) entra en subproblemas similares, es decir, F(19) y F(18). Si resumimos la definición de programación dinámica, dice que un subproblema similar no debe calcularse más de una vez. Aún así, en el caso anterior, el subproblema se calcula dos veces. En el ejemplo anterior, F(18) se calcula dos veces; de manera similar, F(17) también se calcula dos veces. Sin embargo, esta técnica es bastante útil ya que resuelve subproblemas similares, pero debemos tener cuidado al almacenar los resultados porque no somos exigentes en almacenar el resultado que hemos calculado una vez, lo que puede provocar un desperdicio de recursos.

En el ejemplo anterior, si calculamos F(18) en el subárbol derecho, se producirá un enorme uso de recursos y se reducirá el rendimiento general.

La solución al problema anterior es guardar los resultados calculados en una matriz. Primero, calculamos F(16) y F(17) y guardamos sus valores en una matriz. F(18) se calcula sumando los valores de F(17) y F(16), que ya están guardados en una matriz. El valor calculado de F(18) se guarda en una matriz. El valor de F(19) se calcula utilizando la suma de F(18) y F(17), y sus valores ya están guardados en una matriz. El valor calculado de F(19) se almacena en una matriz. El valor de F(20) se puede calcular sumando los valores de F(19) y F(18), y los valores de F(19) y F(18) se almacenan en una matriz. El valor final calculado de F(20) se almacena en una matriz.

¿Cómo funciona el enfoque de programación dinámica?

Los siguientes son los pasos que sigue la programación dinámica:

• Divide el problema complejo en subproblemas más simples.
• Encuentra la solución óptima a estos subproblemas.
• Almacena los resultados de subproblemas (memorización). El proceso de almacenar los resultados de los subproblemas se conoce como memorización.
• Los reutiliza para que el mismo subproblema se calcule más de una vez.
• Finalmente, calcule el resultado del problema complejo.

Los cinco pasos anteriores son los pasos básicos para la programación dinámica. Es aplicable la programación dinámica que tenga propiedades como:

C#

Aquellos problemas que tienen subproblemas superpuestos y subestructuras óptimas. Aquí, subestructura óptima significa que la solución de los problemas de optimización se puede obtener simplemente combinando la solución óptima de todos los subproblemas.

En el caso de la programación dinámica, la complejidad del espacio aumentaría a medida que almacenamos los resultados intermedios, pero la complejidad del tiempo disminuiría.

Enfoques de programación dinámica.

Hay dos enfoques para la programación dinámica:

• Enfoque de arriba hacia abajo
• Enfoque de abajo hacia arriba

Enfoque de arriba hacia abajo

El enfoque de arriba hacia abajo sigue la técnica de memorización, mientras que el enfoque de abajo hacia arriba sigue el método de tabulación. Aquí la memorización es igual a la suma de la recursividad y el almacenamiento en caché. La recursión significa llamar a la función en sí, mientras que el almacenamiento en caché significa almacenar los resultados intermedios.

programación por turnos

Ventajas

• Es muy fácil de entender e implementar.
• Resuelve los subproblemas sólo cuando es necesario.
• Es fácil de depurar.

Desventajas

Utiliza la técnica de recursividad que ocupa más memoria en la pila de llamadas. A veces, cuando la recursividad es demasiado profunda, se producirá la condición de desbordamiento de la pila.

Ocupa más memoria lo que degrada el rendimiento general.

Entendamos la programación dinámica a través de un ejemplo.

 int fib(int n) { if(n<0) error; if(n="=0)" return 0; 1; sum="fib(n-1)" + fib(n-2); } < pre> <p>In the above code, we have used the recursive approach to find out the Fibonacci series. When the value of &apos;n&apos; increases, the function calls will also increase, and computations will also increase. In this case, the time complexity increases exponentially, and it becomes 2<sup>n</sup>.</p> <p>One solution to this problem is to use the dynamic programming approach. Rather than generating the recursive tree again and again, we can reuse the previously calculated value. If we use the dynamic programming approach, then the time complexity would be O(n).</p> <p>When we apply the dynamic programming approach in the implementation of the Fibonacci series, then the code would look like:</p> <pre> static int count = 0; int fib(int n) { if(memo[n]!= NULL) return memo[n]; count++; if(n<0) error; if(n="=0)" return 0; 1; sum="fib(n-1)" + fib(n-2); memo[n]="sum;" } < pre> <p>In the above code, we have used the memorization technique in which we store the results in an array to reuse the values. This is also known as a top-down approach in which we move from the top and break the problem into sub-problems.</p> <h3>Bottom-Up approach</h3> <p>The bottom-up approach is also one of the techniques which can be used to implement the dynamic programming. It uses the tabulation technique to implement the dynamic programming approach. It solves the same kind of problems but it removes the recursion. If we remove the recursion, there is no stack overflow issue and no overhead of the recursive functions. In this tabulation technique, we solve the problems and store the results in a matrix.</p> <p>There are two ways of applying dynamic programming:</p> <ul> <tr><td>Top-Down</td>  </tr><tr><td>Bottom-Up</td>  </tr></ul> <p>The bottom-up is the approach used to avoid the recursion, thus saving the memory space. The bottom-up is an algorithm that starts from the beginning, whereas the recursive algorithm starts from the end and works backward. In the bottom-up approach, we start from the base case to find the answer for the end. As we know, the base cases in the Fibonacci series are 0 and 1. Since the bottom approach starts from the base cases, so we will start from 0 and 1.</p> <p> <strong>Key points</strong> </p> <ul> <li>We solve all the smaller sub-problems that will be needed to solve the larger sub-problems then move to the larger problems using smaller sub-problems.</li> <li>We use for loop to iterate over the sub-problems.</li> <li>The bottom-up approach is also known as the tabulation or table filling method.</li> </ul> <p> <strong>Let&apos;s understand through an example.</strong> </p> <p>Suppose we have an array that has 0 and 1 values at a[0] and a[1] positions, respectively shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-2.webp" alt="Dynamic Programming"> <p>Since the bottom-up approach starts from the lower values, so the values at a[0] and a[1] are added to find the value of a[2] shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-3.webp" alt="Dynamic Programming"> <p>The value of a[3] will be calculated by adding a[1] and a[2], and it becomes 2 shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-4.webp" alt="Dynamic Programming"> <p>The value of a[4] will be calculated by adding a[2] and a[3], and it becomes 3 shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-5.webp" alt="Dynamic Programming"> <p>The value of a[5] will be calculated by adding the values of a[4] and a[3], and it becomes 5 shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-6.webp" alt="Dynamic Programming"> <p>The code for implementing the Fibonacci series using the bottom-up approach is given below:</p> <pre> int fib(int n) { int A[]; A[0] = 0, A[1] = 1; for( i=2; i<=n; i++) { a[i]="A[i-1]" + a[i-2] } return a[n]; < pre> <p>In the above code, base cases are 0 and 1 and then we have used for loop to find other values of Fibonacci series.</p> <p> <strong>Let&apos;s understand through the diagrammatic representation.</strong> </p> <p>Initially, the first two values, i.e., 0 and 1 can be represented as:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-7.webp" alt="Dynamic Programming"> <p>When i=2 then the values 0 and 1 are added shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-8.webp" alt="Dynamic Programming"> <p>When i=3 then the values 1and 1 are added shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-9.webp" alt="Dynamic Programming"> <p>When i=4 then the values 2 and 1 are added shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-10.webp" alt="Dynamic Programming"> <p>When i=5, then the values 3 and 2 are added shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-11.webp" alt="Dynamic Programming"> <p>In the above case, we are starting from the bottom and reaching to the top.</p> <hr></=n;></pre></0)></pre></0)>