Algoritmos y Estructuras de Datos - VJ1215

Ejemplos de errores en el ejercicio 5 del tema 5.3

Piensa por qué no funcionan correctamente las siguientes implementaciones.

Error 1 (en intento de solución no recursiva)

float minimoCostePintura(const vector<vector<float> > & costePintura) {

   int casas = costePintura[0].size();
   vector<vector<float> > resultado(3, vector<float>(casas + 1));

   for (int colorProhibido = 0; colorProhibido < 3; colorProhibido++)
      for (int casa = casas; casa >= 1; casa--)
	 if (casa == casas)
	    resultado[colorProhibido][casa] = 0;
	 else if (colorProhibido == 0)
	    resultado[colorProhibido][casa] = min(costePintura[1][casa] + resultado[1][casa + 1],
					          costePintura[2][casa] + resultado[2][casa + 1]);
	 else if (colorProhibido == 1)
	    resultado[colorProhibido][casa] = min(costePintura[0][casa] + resultado[0][casa + 1],
					          costePintura[2][casa] + resultado[2][casa + 1]);
	 else
	    resultado[colorProhibido][casa] = min(costePintura[0][casa] + resultado[0][casa + 1],
					          costePintura[1][casa] + resultado[1][casa + 1]);
   
   return min({costePintura[0][0] + resultado[0][1],
               costePintura[1][0] + resultado[1][1],
               costePintura[2][0] + resultado[2][1]
              });

}

Solución

El bucle que recorre casas debería ser el externo y el bucle que recorre colores debería ser el interno.

Error 2 (en intento de solución no recursiva)

float minimoCostePintura(const vector<vector<float> > & costePintura) {

   int casas = costePintura[0].size();
   vector<vector<float> > resultado(3, vector<float>(casas + 1));

   for (int casa = 1; casa <= casas; casa++)
      for (int colorProhibido = 0; colorProhibido < 3; colorProhibido++)
	 if (casa == casas)
	    resultado[colorProhibido][casa] = 0;
	 else if (colorProhibido == 0)
	    resultado[colorProhibido][casa] = min(costePintura[1][casa] + resultado[1][casa + 1],
					          costePintura[2][casa] + resultado[2][casa + 1]);
	 else if (colorProhibido == 1)
	    resultado[colorProhibido][casa] = min(costePintura[0][casa] + resultado[0][casa + 1],
					          costePintura[2][casa] + resultado[2][casa + 1]);
	 else
	    resultado[colorProhibido][casa] = min(costePintura[0][casa] + resultado[0][casa + 1],
					          costePintura[1][casa] + resultado[1][casa + 1]);
   
   return min({costePintura[0][0] + resultado[0][1],
               costePintura[1][0] + resultado[1][1],
               costePintura[2][0] + resultado[2][1]
              });

}

Solución

Para hacer los cálculos así, el bucle que recorre las casas debería ir decreciendo desde casas hasta 1, porque el resultado para casa depende del resultado para casa + 1.