¿Qué es la Programación Dinámica

La programación dinámica (en inglés: Dynamic programming, abreviada como DP), es un método utilizado en matemáticas, ceincias de la administración, informática, economía y bioinformmática para resolver problemas complejos mediante la descomposición del problema original en subproblemas más simples. La programación dinámica suele aplicarse a problemas que tienen subproblemas superpuestos y propiedades de subestructura óptima.

 1 /* Matriz.h */
 2 
 3 #pragma once
 4 #ifndef MATRIZ_H
 5 #define MATRIZ_H
 6 
 7 class Matriz
 8 {
 9 public:
10     Matriz();         //Constructor
11     ~Matriz();        //Destructor
12     bool Ejecutar();   //Función de interfaz principal
13 private:
14     int dimension;    //Número de matrices
15     int **costo;      //Almacena el valor óptimo, es decir, la mínima operación
16     int **pos;        //Posición de ruptura
17     int *dimensiones; //Almacena las dimensiones
18 
19     bool LeerDatos();  //Manejo de entrada
20     bool CadenaMatriz();//Algoritmo de cálculo del valor óptimo
21     void Rastro(int i, int j, int **pos);   //Imprime la forma de paréntesis para la multiplicación
22 };
23 
24 #endif

  1 /* Matriz.cpp */
  2 
  3 #define MAX 50
  4 #include <iostream>
  5 #include <stdlib.h>
  6 #include "Matriz.h"
  7 
  8 //Constructor, inicializa variables y asigna memoria para punteros
  9 Matriz::Matriz()
10 {
11     dimension = 0;
12     costo = new int*[MAX];
13     pos = new int*[MAX];
14     for (int i = 0; i < MAX; i++)
15     {
16         costo[i] = new int[MAX];
17         pos[i] = new int[MAX];
18     }
19     dimensiones = new int[MAX];
20 }
21 
22 //Destructor, libera memoria
23 Matriz::~Matriz()
24 {
25     for (int i = 0; i < MAX; i++)
26     {
27         delete[]costo[i];
28         delete[]pos[i];
29     }
30     delete[]costo;
31     delete[]pos;
32     delete[]dimensiones;
33 }
34 
35 //Manejo de entrada desde teclado
36 bool Matriz::LeerDatos()
37 {
38     using namespace std;
39     int n;
40     cout << "Número de matrices: ";
41     cin >> n;
42     dimension = n;
43     cout << "Ingrese dimensiones de la matriz A1: ";
44     cin >> dimensiones[0] >> dimensiones[1];
45     for (int i = 2; i <= dimension; i++)
46     {
47         int temp = dimensiones[i - 1];
48         cout << "Ingrese dimensiones de la matriz A" << i << ": ";
49         cin >> dimensiones[i - 1] >> dimensiones[i];
50         if (dimensiones[i - 1] != temp)
51         {
52             cout << endl << "Dimensiones incorrectas, las matrices no son multiplicables!" << endl;
53             exit(1);
54         }
55     }
56     if (dimensiones != NULL)
57         return true;
58     else
59         return false;
60 }
61 
62 //Algoritmo de cálculo del valor óptimo
63 bool Matriz::CadenaMatriz()
64 {
65     if (NULL == dimensiones)
66         return false;
67     for (int i = 1; i <= dimension; i++)
68         costo[i][i] = 0;
69     for (int longitud = 2; longitud <= dimension; longitud++)
70         for (int i = 1; i <= dimension - longitud + 1; i++)
71         {
72             int j = i + longitud - 1;
73             costo[i][j] = costo[i + 1][j] + dimensiones[i - 1] * dimensiones[i] * dimensiones[j];
74             pos[i][j] = i;
75             for (int k = i + 1; k < j; k++)
76             {
77                 int temp = costo[i][k] + costo[k + 1][j] + dimensiones[i - 1] * dimensiones[k] * dimensiones[j];
78                 if (temp < costo[i][j])
79                 {
80                     costo[i][j] = temp;
81                     pos[i][j] = k;
82                 }
83             }
84         }
85     return true;
86 }
87 
88 //Imprime la forma de combinación de matrices con paréntesis
89 void Matriz::Rastro(int i, int j, int **pos)
90 {
91     using namespace std;
92     if (i == j)
93     {
94         cout << "A" << i;
95     }
96     else if (i + 1 == j)
97     {
98         cout << "(A" << i << "A" << j << ")";
99     }
100     else
101     {
102         cout << "(";
103         Rastro(i, pos[i][j], pos);
104         Rastro(pos[i][j] + 1, j, pos);
105         cout << ")";
106     }
107 }
108 
109 bool Matriz::Ejecutar()
110 {
111     using namespace std;
112     if (Matriz::LeerDatos())
113     {
114         if (Matriz::CadenaMatriz())
115         {
116             Matriz::Rastro(1, dimension, pos);
117             cout << endl;
118             return true;
119         }
120         else
121             return false;
122     }
123     else
124         return false;
125 }
126 

 1 /* Principal.cpp */
 2 
 3 #include "Matriz.h"
 4 
 5 int main()
 6 {
 7     Matriz matriz;
 8     matriz.Ejecutar();
 9     return 0;
10 }