CONCEPTS USED:

Recursion and memoization.

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!! Refer the best sites to learn coding. Look at this example:


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.

<a href="https://mycode.prepbytes.com/problems/dynamic-programming/MONOPOLY&quot; title="Go to mycode.prepbytes.com" target="_blank" rel="noopener noreferrer"><u><strong>See original problem statement here</strong></u></a>

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 <stdio.h>
     int dp[150][150];
     int min(int x,int y)
    {
    if(x<y)
     return x;
     return y;
    }int max(int x,int y)
    {
    if(x>y)
    return x;
    return y;
    }
    int util(int a[],int i,int j){
    // if() 

    if(j<i)return 0;
    if(i+1==j){
        //  cout<<"a"<<i<<" "<<j<<endl;
        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)));
    // cout<<dp[i][j]<<" "<<i<<" "<<j<<endl;
    return dp[i][j];
    }
    int ops(int a[],int n){
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)
            dp[i][j]=-1;
    }
    return util(a,0,n-1);

    }

    int main()
    {
    //code
    int t;
    scanf("%d",&t);
    while(t--){
        int n;
        scanf("%d",&n);
        int a[n];
        for(int i=0;i<n;i++)    
            scanf("%d",&a[i]);
        printf("%d\n",ops(a,n));
    }
    return 0;
    }
 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<n;i++)
            {
                a[i] = sc.nextInt();
            }
        System.out.println( optimalStrategyOfGame(a, n)); }

    } 
    } 
#include<bits/stdc++.h>
     using namespace std;
    int dp[150][150];

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

    if(j<i)return 0;
    if(i+1==j){
        //  cout<<"a"<<i<<" "<<j<<endl;
        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)));
    // cout<<dp[i][j]<<" "<<i<<" "<<j<<endl;
    return dp[i][j];
    }
    int ops(int a[],int n){
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)
            dp[i][j]=-1;
    }
    return util(a,0,n-1);

    }

    int main()
    {
    //code
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int a[n];
        for(int i=0;i<n;i++)    
            cin>>a[i];
        cout<<ops(a,n)<<endl;
    }
    return 0;
    }


*Space complexity: O(NN)**

Previous post MONOPOLY AGAIN
Next post CHOCOLATE DILEMMA

Leave a Reply

Your email address will not be published. Required fields are marked *