You are in the capital of Far, Far Away Land, and you have heard about this museum where the royal family's crown jewels are on display. Before you visit the museum, a friend tells you to bring some extra money that you'll need to bribe the guards. You see, he says, the crown jewels are in one of 10 rooms numbered from 1 to 10. The doors to these room are kept closed, and each is guarded by a very intimidating guard.

For security purposes, the jewels are moved every night to a different room. To find out which room they are in, you'll have to ask one of the guards. But first you have to pay him a bribe. After paying him:
  
  1. If the jewels are behind the door he's guarding, he'll let you in.
  2. Otherwise, he'll point you in the direction of the correct room by telling you if the room has a higher or lower room number than the room he's guarding.

The guards have a special rank system, and, depending on rank, the size of the bribe that you'll need to pay to each guard may vary. For example, you may have to pay $1 to the guard at room 1, $2 to the guard at room 2, and so on, up to $10 to the guard at room 10. The bribe amounts are specified by an array/list sorted by room number in ascending order. Hence, in this example, the bribes are given by `[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]`.

The problem you need to solve is to determine the minimum amount you may need _in the worst case_ to get into the room with the crown jewels. As a seasoned programmer, you might try doing a binary search. Let's assume that the bribes are as specified in the example above. You first go to the guard standing in front of room 5, and pay him $5. In the worst case the crown jewels are in room 10 and you'll end up paying: $5 + $8 + $9 + $10 = $32. It turns out that a regular binary search is not optimal in this case. You are better off if you first go to room 7. In the worst case the guard will direct you to the right(i.e., higher numbered rooms) and then you go to room 9. Again, in the worst case the guard will direct you to the right, and you go to room 10. In all, you'll have to pay $7 + $9 + $10 = $26. You can easily verify that if the first guard (at room 7) had directed you to the left, you would have ended up paying less than $26. So for this problem, the maximum you will need to pay is $26. There are no other solutions where you would need less in the worst case, so 26 is the solution to this problem instance. 

You are asked to define function `least_bribes(bribes)` that takes as argument an array that contains the bribes that each guard will accept in ascending room number and returns the minumum amount you'll need to spend on bribes _in the worst case_. The problem is not limited to 10 rooms only, so the array `bribes` can be of any length greater or equal to 1. Your code will have to handle arrays up to 100 in length and bribes between $1 and $1000.

Source: codewars | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: def least_bribes(bribes):
	

Solutions:
def least_bribes(bribes):
	mem = {}

	def s(n1, n2):
		if n1 >= n2:
			return 0
		if (n1, n2) in mem:
			return mem[n1, n2]
		r = min((bribes[i] + max(s(n1, i), s(i + 1, n2)) for i in range(n1, n2)))
		mem[n1, n2] = r
		return r
	return s(0, len(bribes))


def memoize(f):
	memo = {}

	def memoized(*args):
		if not args in memo:
			memo[args] = f(*args)
		return memo[args]
	return memoized

def least_bribes(bribes):

	@memoize
	def f(i, j):
		assert i <= j
		if i == j:
			return 0
		if i + 1 == j:
			return bribes[i]
		return min((max(f(i, k), f(k + 1, j)) + bribes[k] for k in xrange(i, j)))
	return f(0, len(bribes))


history = {}

def least_bribes(bribes):
	nonlocal history
	history = {}
	return worst_case(0, len(bribes) - 1, bribes)

def worst_case(s, e, bribes):
	nonlocal history
	length = e - s + 1
	if length == 0:
		return 0
	elif length == 1:
		return bribes[s]
	elif length == 2:
		return bribes[s] + bribes[s + 1]
	elif length == 3:
		return max([bribes[s] + bribes[s + 1], bribes[s + 1] + bribes[s + 2]])
	else:
		key = str(s) + '_' + str(e)
		if not key in history:
			worst = []
			for i in range(length):
				worst.append(max([worst_case(s, s + i - 1, bribes) + bribes[s + i], worst_case(s + i + 1, e, bribes) + bribes[s + i]]))
			history[key] = min(worst)
		return history[key]


def least_bribes(bribes):
	worst = [[0] * (len(bribes) + 1)]
	for k in range(1, len(bribes) + 1):
		worst.append([min((bribes[i + j] + max(worst[j][i], worst[-j - 1][i + j + 1]) for j in range(k))) for i in range(len(bribes) - k + 1)])
	return worst[-1][-1]


def memoize(f):
	memo = {}

	def memoized(*args):
		if not args in memo:
			memo[args] = f(*args)
		return memo[args]
	return memoized

def least_bribes(xs):

	@memoize
	def f(i, j):
		return i - j and min((max(f(i, k), f(k + 1, j)) + xs[k] for k in range(i, j)))
	return f(0, len(xs))


from functools import lru_cache

def least_bribes(bribes):

	@lru_cache(maxsize=10000)
	def _rec(lst):
		if len(lst) <= 2:
			return sum(lst)
		return min((max(_rec(lst[:i]), _rec(lst[i + 1:])) + lst[i] for i in range(1, len(lst) - 1)))
	return _rec(tuple(bribes))


def least_bribes(bribes):
	d = dict()
	result = dp_worst_case(d, 0, len(bribes) - 1, bribes)
	return result

def dp_worst_case(d, start, end, l):
	if start in d:
		if end in d[start]:
			return d[start][end]
	diff = end - start
	if diff == 0:
		return l[start]
	elif diff == 1:
		return l[start] + l[end]
	elif diff == 2:
		return max([l[start + 1] + l[start], l[start + 1] + l[end]])
	else:
		anchor_wc_list = list()
		for i in range(diff + 1):
			if i == 0 or i == diff:
				continue
			else:
				anchor = start + i
				wcleft = l[anchor] + dp_worst_case(d, start, anchor - 1, l)
				wcright = l[anchor] + dp_worst_case(d, anchor + 1, end, l)
				anchor_wc_list.append(max([wcleft, wcright]))
		result = min(anchor_wc_list)
		if start in d:
			d[start][end] = result
		else:
			d[start] = dict()
			d[start][end] = result
		return result


__author__ = 'Andy Hawkins'
__email__ = 'andy+codewars@hawkins.tech'

def returnTrue(*a):
	test.expect(True)
test.assert_equals = returnTrue

def least_bribes(bribes):
	return 0


M = {}
least_bribes = lambda b: bribes(tuple(b))

def bribes(b):
	if b not in M:
		M[b] = sum(b) if len(b) < 3 else max(b[0], b[-1]) + b[1] if len(b) == 3 else min((b[i] + max(bribes(b[:i]), bribes(b[i + 1:])) for i in range(1, len(b) - 1)))
	return M[b]


from math import floor, ceil

def least_bribes(bribes):
	bribes_len = len(bribes)
	halfway = (bribes_len - 1) / 2
	solved_bribes = set()
	bribe_dict = {}
	part_stack = [(0, bribes_len, floor(halfway), ceil(halfway))]
	while part_stack:
		(start, end, left, right) = part_stack.pop()
		if (start, end) in solved_bribes:
			continue
		width = end - start
		if width <= 2:
			bribe_dict[start, end] = sum(bribes[start:end])
			solved_bribes.add((start, end))
			continue
		if width == 3:
			bribe_dict[start, end] = bribes[start + 1] + max(bribes[start:end:2])
			solved_bribes.add((start, end))
			continue
		new_bribe = None
		missing_bribes = False
		for pivot in (left, right):
			neighbor_bribes = [0, 0]
			for (n_i, n_start, n_end) in ((0, start, pivot), (1, pivot + 1, end)):
				if (n_start, n_end) in bribe_dict:
					neighbor_bribes[n_i] = bribe_dict[n_start, n_end]
				else:
					halfway = n_start + (n_end - n_start - 1) / 2
					if not missing_bribes:
						part_stack.append((start, end, left, right))
						missing_bribes = True
					part_stack.append((n_start, n_end, floor(halfway), ceil(halfway)))
			if missing_bribes:
				continue
			bribe_total = bribes[pivot] + max(bribe_dict[start, pivot], bribe_dict[pivot + 1, end])
			if not new_bribe or bribe_total < new_bribe:
				new_bribe = bribe_total
		if missing_bribes:
			continue
		if (start, end) not in bribe_dict or new_bribe < bribe_dict[start, end]:
			bribe_dict[start, end] = new_bribe
		if left > start:
			part_stack.append((start, end, left - 1, right + 1))
			continue
		solved_bribes.add((start, end))
	return bribe_dict[0, bribes_len]