# 1884. Egg Drop With 2 Eggs and N Floors
###### tags: `Leetcode` `FaceBook` `Dynamic Programming`
Link: https://hackmd.io/WsVsqlj-TCWD95RcZzi6Ww
## 思路
**因为找的次数有限，所以不能用binary search**
If you drop an egg from i floor (1<=i<=n), then

If the egg breaks, the problem is reduced to x-1 eggs and i - 1 floors
If the eggs does not break, the problem is reduced to x eggs and n-i floors

拓展问题，如果egg的数量不是两个，是k个
就需要用到背包问题的解法了~ 可以参考[这里](https://leetcode.com/problems/egg-drop-with-2-eggs-and-n-floors/discuss/1248069/Recursive-Iterative-Generic)
## Code

class Solution {
    int[] dp;
    public int twoEggDrop(int n) {
        dp = new int[n+1];
        return eggDrop(n);
    }
    public int eggDrop(int n){
        if(dp[n] != 0) return dp[n];
        for(int i = 1;i <= n;i++){
            dp[n] = Math.min(1+Math.max(i-1, eggDrop(n-i)),dp[n]==0?n:dp[n]);   
        }
        return dp[n];
    }
}