Dynamic.txt

def top_down(arr, n):
	memo = {}

	# recursive top down memoized solution
	def solve(i, j):
		if i > j or i >= n or j < 0:
			return 0

		k = (i, j)
		if k in memo:
			return memo[k]

		# if the user chooses ith number, the opponent can choose from i+1th or jth number.
		# if he chooses i+1th number, user is left with [i+2,j] range.
		# if opp chooses jth number, then user is left with [i+1,j-1] range to choose from.
		# Also opponent tries to choose
		# in such a way that the user has minimum value left.
		option1 = arr[i] + min(solve(i+2, j), solve(i+1, j-1))

		# if user chooses jth number, opponent can choose ith number or j-1th number.
		# if opp chooses ith number,user can choose in range [i+1,j-1].
		# if opp chooses j-1th number, user can choose in range [i,j-2].
		option2 = arr[j] + min(solve(i+1, j-1), solve(i, j-2))

		# since the user wants to get maximum money
		memo[k] = max(option1, option2)
		return memo[k]

	return solve(0, n-1)

def bot_up(arr, n):
 
    #Create a table to store
    #solutions of subproblems
    table = [[0 for i in range(n)]
             for i in range(n)]
 
    # Fill table using above recursive
    # formula. Note that the table is
    # filled in diagonal fashion
    # from diagonal elements to
    # table[0][n-1] which is the result.
    for gap in range(n):
        for j in range(gap, n):
            i = j - gap
 
            # Here x is value of F(i + 2, j),
            # y is F(i + 1, j-1) and z is
            # F(i, j-2) in above recursive
            # formula
            x = 0
            if((i + 2) <= j):
                x = table[i + 2][j]
            y = 0
            if((i + 1) <= (j - 1)):
                y = table[i + 1][j - 1]
            z = 0
            if(i <= (j - 2)):
                z = table[i][j - 2]
            table[i][j] = max(arr[i] + min(x, y),
                              arr[j] + min(y, z))
    return table[0][n - 1]
 
 

# Test Code
list1 = [5, 3, 7, 10]
n = len(list1)
print('Maximum Profit of P1 using Top Down approach = ', top_down(list1, n))

print('Maximum Profit of P1 using Bottom Up approach = ', bot_up(list1, n))
 
list2 = [8, 15, 3, 7]
n = len(list2)
print('Maximum Profit of P1 using Top Down approach = ',top_down(list2, n))
print('Maximum Profit of P1 using Bottom Up approach = ', bot_up(list2, n))

list3 = [20, 30, 2, 2, 2, 10]
n = len(list3)
print( 'Maximum Profit of P1 using Top Down approach = ',top_down(list3, n))
print('Maximum Profit of P1 using Bottom Up approach = ', bot_up(list3, n))