Optimal Strategy For A Game

#1

question–>
https://practice.geeksforgeeks.org/problems/optimal-strategy-for-a-game-1587115620/1#
code–>


showing TLE!!! help

#2

Hey @sheikhhaji18
Code is good there is no further optimization in Top Down Approach
It must be expecting Bottom up dp solution

#4

Auto-correct :sweat_smile: . . . . …

#5

hi ,it is working fine,i saw a code in comment section memoization is working fine!!

int dp[101][101];

int solve(int arr[], int i, int j){
    if(i>j)
        return 0;
    if(dp[i][j] != -1)
        return dp[i][j];
        
    return dp[i][j] = max(min(solve(arr, i+1, j-1)+arr[i] , solve(arr, i+2, j)+arr[i])
                , min(solve(arr, i+1, j-1)+arr[j], solve(arr, i, j-2)+arr[j]));
}

long long maximumAmount(int arr[], int n) 
{
    // Your code here
    memset(dp, -1, sizeof(dp));
    return solve(arr, 0, n-1);
}
#6

Yeah reduce the dp array size to 100 X 100
urs will also work
I havent checked the constraints earlier
Memset is taking extra time when u are creating 5000x5000 dp