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.

Ejemplo de solución incorrecta 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]
              });

}

¿Por qué es incorrecta?

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

Ejemplo de solución incorrecta 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]
              });

}

¿Por qué es incorrecta?

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.