// 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 colorObligado,
                         int casa) {
   
   // Minimo coste de pintar desde esa casa hasta la ultima si en esa casa SE DEBE USAR ese color

   int casas = costePintura[0].size();

   float resultado;

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

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

   return min({minimoCostePintura(costePintura, 0, 0),
               minimoCostePintura(costePintura, 1, 0),
               minimoCostePintura(costePintura, 2, 0)
              });

}
*/

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

/*
#define DESCONOCIDO -1

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

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

   return resultado[colorObligado][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({minimoCostePintura(costePintura, 0, 0, resultado),
               minimoCostePintura(costePintura, 1, 0, resultado),
               minimoCostePintura(costePintura, 2, 0, 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 >= 0; casa--)
      for (int colorObligado = 0; colorObligado < 3; colorObligado++)
	 if (casa == casas)
	    resultado[colorObligado][casa] = 0;
	 else if (colorObligado == 0)
	    resultado[colorObligado][casa] = costePintura[colorObligado][casa] + min(resultado[1][casa + 1],
								                       resultado[2][casa + 1]);
	 else if (colorObligado == 1)
	    resultado[colorObligado][casa] = costePintura[colorObligado][casa] + min(resultado[0][casa + 1],
 								                       resultado[2][casa + 1]);
	 else if (colorObligado == 2)
	    resultado[colorObligado][casa] = costePintura[colorObligado][casa] + min(resultado[0][casa + 1],
								                       resultado[1][casa + 1]);
   
   return min({resultado[0][0],
               resultado[1][0],
               resultado[2][0]
              });

}
*/

/***************************************************************************
 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 >= 0; casa--) {

      resultado[0][casa] = costePintura[0][casa] + min(resultado[1][casa + 1],
						       resultado[2][casa + 1]);

      resultado[1][casa] = costePintura[1][casa] + min(resultado[0][casa + 1],
						       resultado[2][casa + 1]);

      resultado[2][casa] = costePintura[2][casa] + min(resultado[0][casa + 1],
						       resultado[1][casa + 1]);
   }

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

}
*/

/***************************************************************************
 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;

}