// Descomenta la version que quieras probar

#include <iostream>
#include <vector>
#include <algorithm> // min({...})

using namespace std;

/***************************************************************************
 VERSION 1: RECURSIVA, INEFICIENTE
 ***************************************************************************/

/*
float minimoCostePintura(const vector<vector<float> > & costePintura,
			 int colorProhibido,
			 int casa) {
   
   // Minimo coste de pintar desde esa casa hasta la ultima si en esa casa NO SE PUEDE USAR ese color
   
   int casas = costePintura[0].size();

   float resultado;
   
   if (casa == casas)
      resultado = 0;
   else  if (colorProhibido == 0)
      resultado = min(costePintura[1][casa] + minimoCostePintura(costePintura, 1, casa + 1),
		      costePintura[2][casa] + minimoCostePintura(costePintura, 2, casa + 1));
   else if (colorProhibido == 1)
      resultado = min(costePintura[0][casa] + minimoCostePintura(costePintura, 0, casa + 1),
		      costePintura[2][casa] + minimoCostePintura(costePintura, 2, casa + 1));
   else
      resultado = min(costePintura[0][casa] + minimoCostePintura(costePintura, 0, casa + 1),
		      costePintura[1][casa] + minimoCostePintura(costePintura, 1, casa + 1));
   
   return resultado;

}

float minimoCostePintura(const vector<vector<float> > & costePintura) {
   
   return min({costePintura[0][0] + minimoCostePintura(costePintura, 0, 1),
	       costePintura[1][0] + minimoCostePintura(costePintura, 1, 1),
	       costePintura[2][0] + minimoCostePintura(costePintura, 2, 1)
              });
   
}
*/

/***************************************************************************
 VERSION 2: RECURSIVA, EFICIENTE
 ***************************************************************************/

/*
#define DESCONOCIDO -1

float minimoCostePintura(const vector<vector<float> > & costePintura,
			 int colorProhibido,
			 int casa,
			 vector<vector<float> > & resultado) {
   
   int casas = costePintura[0].size();

   if (resultado[colorProhibido][casa] == DESCONOCIDO)
      if (casa == casas)
	 resultado[colorProhibido][casa] = 0;
      else  if (colorProhibido == 0)
	 resultado[colorProhibido][casa] = min(costePintura[1][casa] + minimoCostePintura(costePintura, 1, casa + 1, resultado),
				               costePintura[2][casa] + minimoCostePintura(costePintura, 2, casa + 1, resultado));
      else if (colorProhibido == 1)
	 resultado[colorProhibido][casa] = min(costePintura[0][casa] + minimoCostePintura(costePintura, 0, casa + 1, resultado),
				               costePintura[2][casa] + minimoCostePintura(costePintura, 2, casa + 1, resultado));
      else
	 resultado[colorProhibido][casa] = min(costePintura[0][casa] + minimoCostePintura(costePintura, 0, casa + 1, resultado),
				               costePintura[1][casa] + minimoCostePintura(costePintura, 1, casa + 1, resultado));
   
   return resultado[colorProhibido][casa];
  
}

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

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

   return min({costePintura[0][0] + minimoCostePintura(costePintura, 0, 1, resultado),
               costePintura[1][0] + minimoCostePintura(costePintura, 1, 1, resultado),
               costePintura[2][0] + minimoCostePintura(costePintura, 2, 1, resultado)
              });

}
*/

/***************************************************************************
 VERSION 3: NO RECURSIVA, EFICIENTE
 ***************************************************************************/

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

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

   for (int casa = casas; casa >= 1; 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]
              });

}
*/

/***************************************************************************
 VERSION 3.1: NO RECURSIVA, EFICIENTE, SIMPLIFICADA
 ***************************************************************************/

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

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

   resultado[0][casas] = 0;
   resultado[1][casas] = 0;
   resultado[2][casas] = 0;

   for (int casa = casas - 1; casa >= 1; casa--) {

      resultado[0][casa] = min(costePintura[1][casa] + resultado[1][casa + 1],
			       costePintura[2][casa] + resultado[2][casa + 1]);
      
      resultado[1][casa] = min(costePintura[0][casa] + resultado[0][casa + 1],
			       costePintura[2][casa] + resultado[2][casa + 1]);
      
      resultado[2][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]
              });

}
*/

/***************************************************************************
 EJEMPLO
 ***************************************************************************/

int main () {

   vector<vector<float> > ejemploCostePintura = { {300, 600,  200, 1000, 1500, 500, 900},
                                                  {400, 1600, 400, 700,  1200, 400, 200},
                                                  {500, 1300, 600, 100,  300,  500, 800} };

   float resultado = minimoCostePintura(ejemploCostePintura);
   cout << "Minimo coste pintura: " << resultado << endl;
   if (resultado == 3300)
      cout << "OK" << endl;
   else
      cout << "MAL" << endl;

}