Q46 Super Egg Drop - LeetCode 887
Thu Mar 30 2023 12:38:58 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
class Solution {
public int superEggDrop(int eggs, int floors) {
//dp ques 46 of playlist
//if floors == 1 return 1 , if 0 return 0 ;
if(floors == 0) return 0 ;
if(floors == 1) return 1;
if(eggs == 0) return -1;
if(eggs == 1) return floors; //minimum attempts will be total floors
//let eggs be on rows and floors be on cols
//+1 for 0 eggs and 0 floors
int dp[][] = new int[eggs+1][floors+1];
//1st row ->invalid , 2nd row -> no.of floors will be answer ,1st col->0
for(int i = 1 ; i < eggs+1 ;i++){
for(int j = 1 ; j < floors+1 ; j++){
if(i == 1)
dp[i][j] = j;
else{
// taking max of all options and then taking min of those
int min = Integer.MAX_VALUE;
for(int b = j-1 , a = 0 ; b>=0 ; a++ , b--){
int breaks = dp[i][b]; //egg breaks
int safe = dp[i-1][a]; //egg doesn't breaks
int val = Math.max(safe , breaks);
min = Math.min(val , min);
}
dp[i][j] = min+1;
}
}
}
return dp[eggs][floors];
}
}
content_copyCOPY
https://leetcode.com/problems/super-egg-drop/
Comments