C++ code with explanation fo logic. But getting runtime err for god knows what reason


#1
int Solution::solve(int A, int B) {
    // A -> no of eggs B-> no of total floors in building
    //int dp[A+1][B+1];
    //memset(dp, 0, sizeof(dp));
    vector<vector<int>> dp(A+1,vector<int>(B+1,0));
    
    // EXPLANATION: n->floors e->eggs count
    // 1. F[n][e] = min(max(F[n-x][e], F[x-1][e-1]) + 1)
    //             x=1->n-1
    // minimize the max(worst case) to get least no of tries. First term is 
    // when egg doesnt break. e remains same. We need to focus on higher floors (n-x)
    // Second term is when egg breaks(e-1 eggs left). So to find breakpoint floor we go 
    // down (x-1). The 3rd term(+1) is for one try(dropping egg) done on current floor
    
    // 2 constrains: F[1][e] = 1. one floor left and any no of eggs -> only 1 try 
    // F[n][1] = n. n floors and one egg left. Start from bottom floor and keep dropping 
    //same egg in each floor till it breaks (worst case N floors)
    
    for(int i = 1; i<=B; i++) dp[i][1] = i; // 2nd constraint as seen above
    for(int i = 1; i<=A; i++) dp[1][i] = 1; // 1st constraint
    
    for(int i = 2; i<=B; i++){ // building 
        for(int j = 2; j<=A; j++){ // egg
            dp[i][j] = INT_MAX;
            // x = 1 to n-1
            for(int x = 1; x<i; x++){
                int brokenEggResult = dp[x-1][j-1];
                int unbrokenEggResult = dp[i-x][j];
                int temp = max(brokenEggResult, unbrokenEggResult) + 1;
                if(temp < dp[i][j]) dp[i][j] = temp;
            }
        }
    }
    
    // its a bottoms up approach. So largest cell (bottom most rightmost val) is the ans
    return dp[A][B];
    
    
}

If you find out why I’m getting the error, so let me know in the comments…


#2

They are actually expecting a binary search answer! See geeks for geeks !


#3

Your dp declared is dp[A+1][B+1]
and your dp logic is based on dp[B+1][A+1]