254.Drop Eggs

There is a building of n floors. If an egg drops from the k th floor or above, it will break. If it's dropped from any floor below, it will not break.

You're given two eggs, Find k while minimize the number of drops for the worst case. Return the number of drops in the worst case.

Clarification
For n = 10, a naive way to find k is drop egg from 1st floor, 2nd floor ... kth floor. But in this worst case (k = 10), you have to drop 10 times.

Notice that you have two eggs, so you can drop at 4th, 7th & 9th floor, in the worst case (for example, k = 9) you have to drop 4 times.

Example
Given n = 10, return 4.
Given n = 100, return 14.

public class Solution {
/**
 * @param n an integer
 * @return an integer
 */
public int dropEggs(int n) {
    // Write your code here
    long sum = 0;
    int inc = 1;
    while (sum < n) {
        sum += inc;
        inc++;
    }
    return inc - 1;
}
}
//假设最少drop x次，则必须从x层开始扔，因为当第一个蛋碎后，第二个蛋还需要扔 x － 1 次。蛋不碎，还得扔 x － 1次，所以得从 x ＋ x － 1层开始扔。 x ＋ (x - 1) + (x - 2) ... + 1 >= 100

以下做法超时：

public class Solution {
/**
 * @param n an integer
 * @return an integer
 */
public int dropEggs(int n) {
    // Write your code here
    int[] state = new int[n + 1];
    state[1] = 1;
    for (int i = 2; i < n + 1; i++) {
        int min = Integer.MAX_VALUE;
        for (int j = 1; j < i + 1; j++) {
            min = Math.min(Math.max(j - 1, state[i - j]),min);
        }
        state[i] = min + 1;
    }
    return state[n];
}
}
// state(N) = min{max(t - 1, state(N - t))} + 1 | t = 1 .... N