classSolution{public:inttwoEggDrop(intn){returnsuperEggDrop(2,n);}private:vector<vector<int>>dp;intsuperEggDrop(intK,intN){// dp[k][n] := min # of moves to know F with k eggs and n floorsdp.resize(K+1,vector<int>(N+1,-1));returndrop(K,N);}intdrop(intk,intn){if(k==0)// no eggs -> donereturn0;if(k==1)// one egg -> drop from 1-th floor to n-th floorreturnn;if(n==0)// no floor -> donereturn0;if(n==1)// one floor -> drop from that floorreturn1;if(dp[k][n]!=-1)returndp[k][n];// broken[i] := drop(k - 1, i - 1) is increasing w/ i// unbroken[i] := drop(k, n - i) is decreasing w/ i// dp[k][n] := 1 + min(max(broken[i], unbroken[i])), 1 <= i <= n// find the first index i s.t broken[i] >= unbroken[i],// which minimizes max(broken[i], unbroken[i])intl=1;intr=n+1;while(l<r){constintm=(l+r)/2;constintbroken=drop(k-1,m-1);constintunbroken=drop(k,n-m);if(broken>=unbroken)r=m;elsel=m+1;}returndp[k][n]=1+drop(k-1,l-1);}};
JAVA
classSolution{publicinttwoEggDrop(intn){returnsuperEggDrop(2,n);}privateint[][]dp;privateintsuperEggDrop(intK,intN){// dp[k][n] := min # of moves to know F with k eggs and n floorsdp=newint[K+1][N+1];Arrays.stream(dp).forEach(row->Arrays.fill(row,-1));returndrop(K,N);}privateintdrop(intk,intn){if(k==0)// no eggs -> donereturn0;if(k==1)// one egg -> drop from 1-th floor to n-th floorreturnn;if(n==0)// no floor -> donereturn0;if(n==1)// one floor -> drop from that floorreturn1;if(dp[k][n]!=-1)returndp[k][n];// broken[i] := drop(k - 1, i - 1) is increasing w/ i// unbroken[i] := drop(k, n - i) is decreasing w/ i// dp[k][n] := 1 + min(max(broken[i], unbroken[i])), 1 <= i <= n// find the first index i s.t broken[i] >= unbroken[i],// which minimizes max(broken[i], unbroken[i])intl=1;intr=n+1;while(l<r){finalintm=(l+r)/2;finalintbroken=drop(k-1,m-1);finalintunbroken=drop(k,n-m);if(broken>=unbroken)r=m;elsel=m+1;}returndp[k][n]=1+drop(k-1,l-1);}}
Login to Codeflu
Log in to stay update and get notify on new arrivals.