Hi, can someone help me on this question about dynamic programming please? Consi

Question

Hi, can someone help me on this question about dynamic programming please?

Consider the following game. You are given a set of n numbers x1, x2, . . . , xn. There

are two players Alice and Bob, who alternate moves, and each want to maximize their own value.

Alice moves first. When it is a player’s turn, she/he can select to take either the last element of the

current sequence or the first element of the current sequence. The optimal value of this problem is the

maximum value Alice (the player who moves first) can guarantee for herself no matter how Bob plays.

For example, if the sequence is: 5, 1, 10;

then Alice can guarantee 11, which she gets by taking the 10. And then no matter which end Bob takes

she gets at least one more. In the sequence: 5, 50, 60, 50, 60, 50, 60, 15;

Alice can guarantee herself 5+3*60 by taking the 5 at the left end first. No matter what Bob takes

next, Alice will then be able to take all the 60 values. In contrast, taking the 15 on the right end first,

Bob can get the 60 values for himself.

Give a polynomial time algorithm that finds the maximum value Alice can guarantee for herself (no

need to solve for the optimal strategy itself, just the value, and regardless of whether Alice win the

game or not, just find the maximum possible value for Alice). Your answer should include the algorithm,

a proof for the algorithm and the extimated runtime.

Explanation / Answer

#include <iostream>
#include <algorithm>

using namespace std;

int dp(int A[], int i, int n){
if(i==n){
return A[i];
}
if(i>n){
return 0;
}
  
else return max (A[i]+min(dp(A,i+2,n),dp(A,i+1,n-1)) ,A[n]+min(dp(A,i+1,n-1),dp(A,i,n-2)));
  
}

for dynamic

#include <iostream>
#include <algorithm>

using namespace std;

int dp(int A[], int i, int n){
int C[n+1][n+1] = {0};
if(i==n){
C[i][n]=A[i];
return C[i][n];
}
if(i>n){
C[i][n]=0;
return C[i][n];
}
if (C[i+2][n]==0){
C[i+2][n]=dp(A,i+2,n);
}
if (C[i+1][n-1]==0){
C[i+1][n-1]=dp(A,i+1,n-1);
}
if (C[i][n-2]==0){
C[i][n-2]=dp(A,i,n-2);
}
  
  
else return max (A[i]+min(C[i+2][n],C[i+1][n-1]) ,A[n]+min(C[i+1][n-1],C[i][n-2]));
  
}

int main() {
int A[8]= {5, 50, 60, 50, 60, 50, 60, 15};
int B[2]={10,5};
cout<<dp(A,0,7);
}

int main() {
int A[8]= {5, 50, 60, 50, 60, 50, 60, 15};
//cout<<A[7];
int B[3]={10,5,1};
cout<<dp(A,0,7);
}

Time Analysis

We have dp(A, i , n)

since we need to calculate each dp(A,i,n) just once for different n and i.

So maximum time it can take is same as

no of line in our program * no of different value of i * no of different value of n

= const*n*n = K n2

Proof

Here we are making all possiblities and every time we are backtracking to get the maximum value so this must give maximum solution

Note however this proof is just for intuition, if you want formal proof then do comment

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.