Python : Pure recursive solution with dict based memoization


#1
class Solution:
    def __init__(self):
        self.cache = {}
        
    # @param A : list of integers
    # @return an integer
    def maxc(self, A, start, end):
        key = "{}:{}".format(start,end)
        if key in self.cache:
            return self.cache[key]
        
        if end - start == 1:
            return max(A[start], A[end])
        else:
            v1 = A[end] + min(self.maxc(A, start, end-2),self.maxc(A, start+1, end-1))
            v2 = A[start] + min(self.maxc(A, start + 1, end-1),self.maxc(A, start+2, end))
            res = max(v1,v2)
            self.cache[key] = res
            
            return res
            
    def maxcoin(self, A):
        return self.maxc(A, 0, len(A)-1)