MONOPOLY

Last Updated on March 30, 2022 by Ria Pathak

CONCEPTS USED:

Recursion and memorization.

DIFFICULTY LEVEL:

Medium.

PROBLEM STATEMENT$($SIMPLIFIED$)$:

There are notes having values V1,V2,V3…Vn arranged in a row. You and your friend take turns alternatively. In each turn you can select either the first or the last note in the row and remove it. The note’s value gets added to your balance. Now you need to determine how you should select the notes such that in the end you have more cash than your friend.
You always go first.

For Example :

2
4
5 3 7 15
4
8 15 1 6

For first testcase
You - 15
Friend - 7
You - 5
Friend - 3
So total 15 + 5 =20

OBSERVATION:

You have to think about your opponent’s move means options available for the your opponent once you are done with the move, What your opponent will pick (he is equally clever and tries to leave you with minimum values to be chosen from) and then what you will chose.

SOLVING APPROACH:

WRONG APPROACH:
GREEDY .You may think that selecting the maximum value from the two ends will get you the maximum sum of notes.But that’s wrong!!

Look at this example:

14 20 6 8
If you use greedy technique , you would end up with 14+8= 22 notes and your opponent would win with 20+6=26 notes. 
Whereas the correct answer to this test case will be:
you :20+8=28 notes,
your opponent: 6+14=20 notes.

You are encouraged to try this problem ,before looking at the solution.

See original problem statement here

Have you noticed that your opponent is equally clever??
We can clearly see that each player is making the move by keeping in mind the two moves which can be made in future and pick the best of them.
Let’s make it more clear- Suppose we have coins lined up from Ci to Cj with the values from Vi to Vj respectively.

In every move you have 2 options –

Either pick the ith coin (from starting)
OR pick the jth coin ( from the end).

Let’s discuss both the options

You the ith coin (from starting)

1. You choose the ith coin with value Ci: The opponent either chooses (i+1)^th coin or jth coin. The opponent intends to choose the coin which leaves you with minimum value.
   i.e. The user can collect the value Ci + min(F(i+2, j), F(i+1, j-1) ).

2. You choose the jth coin with value Cj: The opponent either chooses ith coin or (j-1)^th coin. The opponent intends to choose the coin which leaves you with minimum value.
   i.e. The user can collect the value Cj + min(F(i+1, j-1), F(i, j-2) ).
   Following is recursive solution that is based on above two choices. We take the maximum of two choices.

   F(i, j) = Max { Ci + Min{F(i+2,j), F(i+1, j-1)} ,
         Cj + Min{F(i+1,j-1), F(i, j-2)}}

SOLUTIONS:

 #include 
     int dp[150][150];
     int min(int x,int y)
    {
    if(xy)
    return x;
    return y;
    }
    int util(int a[],int i,int j){
    // if() 

    if(j





						 

#include
     using namespace std;
    int dp[150][150];

    int util(int a[],int i,int j){
    // if() 

    if(j>t;
    while(t--){
        int n;
        cin>>n;
        int a[n];
        for(int i=0;i>a[i];
        cout<
						 

 import java.util.*;
    import java.io.*;
     class monopoly { 
    static int optimalStrategyOfGame( 
        int arr[], int n) 
    { 
        int table[][] = new int[n][n]; 
        int gap, i, j, x, y, z; 
        for (gap = 0; gap < n; ++gap) { 
            for (i = 0, j = gap; j < n; ++i, ++j) { 
                x = ((i + 2) <= j) 
                        ? table[i + 2][j] 
                        : 0; 
                y = ((i + 1) <= (j - 1)) 
                        ? table[i + 1][j - 1] 
                        : 0; 
                z = (i <= (j - 2)) 
                        ? table[i][j - 2] 
                        : 0; 

                table[i][j] = Math.max( 
                    arr[i] + Math.min(x, y), 
                    arr[j] + Math.min(y, z)); 
            } 
        } 

        return table[0][n - 1]; 
    } 
    public static void main(String[] args) 
    { 
      Scanner sc = new Scanner(System.in);
        int t= sc.nextInt();
        while(t-- >0 ){
            int n = sc.nextInt();
            int a[]=new int[n];
            for(int i=0;i
						 

dp = [[0 for i in range(150)] for j in range(150)]

def util(a, i, j):
	
	global dp

	if(j < i):
		return 0

	if(i + 1 == j):
		return max(a[i],a[j])

	if(dp[i][j]!=-1):
		return dp[i][j]
	
	dp[i][j] = max(a[i] + min(util(a, i + 1, j - 1),util(a, i + 2, j)),a[j] + min(util(a, i + 1, j - 1), util(a, i, j - 2)))
	
	return dp[i][j]
	
def ops( a, n):
	
	for i in range(n):

		for j in range(n):

			dp[i][j] = -1
	
	return util(a, 0, n - 1)
	

for _ in range(int(input())):

	n = int(input())
	a = list(map(int,input().split()))
	print(ops(a, n))

This article tried to discuss the concept of Recursion and memorization. Hope this blog helps you understand and solve the problem. To practice more problems on Recursion and memorization you can check out MYCODE | Competitive Programming.