Why tle occur i sove it by binary search technique


#1

Comment body govector<vector> dp(A+1,vector(B+1,-1));

if(B==0||B==1) return B; //if no. of floor 0 , 1 return n:
if(A==1) return B; // if 1 egg return number of floor
if(dp[A][B]!=-1)
return dp[A][B];
int ans=INT_MAX;
int l=1,h=B,temp=0;

    while(l<=h)
    {
        int mid=(l+h)/2;
        int left=solve(A-1,mid-1);   
        int right=solve(A,B-mid) ;   
        temp=1+max(left,right);         
        if(left<right){  
            
          l=mid+1;                    
        }
        else                            
        {    
            h=mid-1;
        }
        ans=min(ans,temp);              
    
    }
   // return dp[k][n]=ans;

return dp[A][B]=ans;es here.


#2

This code won’t work as it’ll give the best case which is logn and we have to find the worst case for the optimum solution. And if you iterate 1 to h and look closely at the temp of each then you’ll find a pattern i.e., first inc and then dec. So think about it.