Curso 2023/2024
Piensa por qué no funcionan correctamente las siguientes implementaciones.
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] }); }
El bucle que recorre casas debería ser el externo y el bucle que recorre colores debería ser el interno.
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] }); }
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
.