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.

Difficulty: interview

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[k][i] is the minimal amount of bribes spent in the worst case
    # for a subarray of length k beginning at index i.
    worst = [[0] * (len(bribes) + 1)]
    for k in range(1, len(bribes) + 1):
        #worst.append([min(bribes[j] + max(worst[j-i][i], worst[i+k-j-1][j+1]) for j in range(i, i + k)) for i in range(len(bribes) - k + 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):
    # DP to re-use results
    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:
        # For 3 doors, the worst case is having to open 2 (doors [2,1] or [2,3]). You never have to open 3.
        return max([l[start+1] + l[start], l[start+1] + l[end]])
    else:
        anchor_wc_list = list()
        # Iterate over every anchor door ...
        for i in range(diff + 1):
            # ... except the first and last one of a (sub)list (they don't have to be visited "first")
            if i == 0 or i == diff:
                continue
            else:
                # work on the nonlocal list scale instead of the local loop list scale
                anchor = start + i
                # get left and right "branch" worst cases for the resp. anchor
                wcleft = l[anchor] + dp_worst_case(d, start, anchor - 1, l)
                wcright = l[anchor] + dp_worst_case(d, anchor + 1, end, l)
                # find the "worse" worst case of the left and right branch
                anchor_wc_list.append(max([wcleft, wcright]))
        # the result is the "best" worst case for all anchors
        result = min(anchor_wc_list)
        
        # save results for DP
        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):
    # Hack The Planet!
    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)]