#include <algorithm>
#include <iostream>
#include <limits>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

string get_key(int color, int index) {
  string res;
  res.append(to_string(color));
  res.append("-");
  res.append(to_string(index));
  return res;
}

int cost_from_here(const vector<vector<int>>& costs, int index_house,
                   int prev_color, unordered_map<string, int>* cost_map) {
  if (index_house == costs.size()) {
    return 0;
  }
  string key = get_key(prev_color, index_house);
  auto it = cost_map->find(key);
  if (it != cost_map->end()) {
    return it->second;
  }
  int cost = numeric_limits<int>::max();
  for (int c : {0, 1, 2}) {
    if (c != prev_color) {
      cost = min(cost, costs[index_house][c] +
                           cost_from_here(costs, index_house + 1, c, cost_map));
    }
  }
  (*cost_map)[key] = cost;
  return cost;
}

vector<int> get_other_colors(int c) {
  unordered_set<int> s = {0, 1, 2};
  s.erase(c);
  return vector<int>(s.begin(), s.end());
}

int cost_from_here_dp(const vector<vector<int>>& costs) {
  if (costs.empty()) {
    return 0;
  }
  vector<int> prev(3, 0);
  for (int i = costs.size() - 1; i >= 0; i--) {
    vector<int> cur(3, numeric_limits<int>::max());
    for (int c : {0, 1, 2}) {
      vector<int> other_colors = get_other_colors(c);
      for (int oc : other_colors) {
        cur[c] = min(cur[c], prev[oc] + costs[i][c]);
      }
    }
    swap(prev, cur);
  }
  return min(prev[0], min(prev[1], prev[2]));
}

class Solution {
public:
  int minCost(const vector<vector<int>>& costs) {
    return cost_from_here_dp(costs);
    // unordered_map<string, int> cost_map;
    // return cost_from_here(costs, /*index_house=*/0, /*prev_color=*/-1,
    //                       &cost_map);
  }
};

int main() {
  Solution().minCost({{17, 2, 13}, {16, 16, 5}, {14, 3, 19}, {40, 20, 4}});
  return 0;
}