holidays.py

"""
Bound by our cache table which is every combination of subproblem, so
cities * months. Worst case we fill each of those cells (every city is
neighbors with every other city); filling in a cell takes worst case #cities
work (if it's neighbors with every other city) giving us overall bounding
O( cities * months * cities )
"""

from collections import defaultdict
table = defaultdict(dict)

def best_days_off(city, monthsleft):
  # First try to hit cache
  if city in table and monthsleft in table[city]:
    return table[city][monthsleft]

  # Recursive base case
  if monthsleft == 0:
    return holidays_calendar(city, 12-monthsleft)

  # Otherwise perform recursion
  paths = [best_days_off(c, monthsleft-1) for c in neighbors(city)] # Try all paths
  best = max(paths) + holidays_calendar(city, 12-monthsleft) # Take the best result of all possible forks
  table[city][monthsleft] = best # Cache this work for future
  return best