계란K개를 얻을 수 있고 1층부터 N층까지 모두 N층 건물을 이용할 수 있다.
모든 알의 기능은 똑같다. 만약 한 알이 깨진다면, 너는 다시는 그것을 떨어뜨릴 수 없다.
너는 층F이 존재한다는 것을 알고 있다. 만족0 <= F <= N은 F보다 높은 층에서 떨어진 계란은 모두 깨지고, F층이나 그보다 낮은 층에서 떨어진 계란은 깨지지 않는다.
매번 이동할 때마다 계란 하나를 꺼내서 (완전한 계란이 있다면) 어느 층X에서 던져도 된다. (만족 1 <= X <= N너의 목표는 F 의 값이 얼마인지 확실히 아는 것이다.F의 초기값이 어떻든지 간에F의 값의 최소 이동 횟수는 얼마입니까?
 
예 1:

  ：K = 1, N = 2
  ：2
  ：
    1    。     ，       F = 0 。
  ，    2    。     ，       F = 1 。
     ，         F = 2 。
  ，              2      F    。

예 2:

  ：K = 2, N = 6
  ：3

예 3:

  ：K = 3, N = 14
  ：4

 
팁:

1 <= K <= 100

1 <= N <= 10000

 

dp[k][m]는 k개의 계란이 m보에서 측정할 수 있는 최대 층수를 표시하기 때문에 우리는 문제를 k<=K로 바꿀 때 가장 작은 m를 찾아 dp[k][m]>=N으로 전환시킨다.우리는 dp[k][m]의 dp 전략을 고려할 것이다.만약에 k개의 계란이 m단계에 있을 때 우리는 X층에서 계란을 던졌다. 두 가지 결과: 1.계란이 깨지지 않았으니 우리는 X+dp[k][m-1]층의 결과를 확정할 수 있다.2. 계란이 깨지면 우리는 Y+dp[k-1][m-1]층의 결과(X위에 Y층이 있다고 가정)를 확정할 수 있다. 왜냐하면 우리는 X이상의 층이 계란을 던져서 모두 깨지는 것을 알고 있기 때문이다.

그래서 우리는 이번에 계란을 던지면 dp[k][m-1]+dp[k-1][m-1]+1(이층)의 결과를 확정할 수 있다.또 계란이 없으면 한 층도 측정할 수 없고, 계란이 한 층만 있으면 한 층만 측정할 수 있다.그러니까 점차적인 공식.dp[k][0]=0; dp[1][m]=m;(m부터 N까지)dp[k][m]=dp[k][m-1]+dp[k-1][m-1]+1

이 시간의 복잡도 O (K*logN)

class Solution 
{
public:
    int superEggDrop(int K, int N)
    {
        int dp[K+2][N+2];
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 0;
        for (int m = 1; m <= N; m++) 
        {
            dp[0][m] = 0;
            for (int k = 1; k <= K; k++)
            {
                dp[k][m] = dp[k][m-1] + dp[k-1][m-1] + 1;
                if (dp[K][m] >= N)
                {
                    return m;
                }
            }
        }
    return N;
    }
};

비교적 이해하기 쉬운 문법을 말한다. dp[n][k]를 가정하면 k개의 계란이 n층을 측정하는 데 적어도 몇 걸음이 걸릴지 나타낸다.만약 우리가 지금 i층에서 계란을 던진다면 우리는 두 가지 결과가 있다.계란이 깨지면 우리는 이때 k-1개의 계란으로 i-1층을 측정해야 하기 때문에 적어도 dp[i-1][k-1]보2.계란이 깨지지 않았는데 우리는 아직 k개의 계란을 가지고 n-i층을 측정하기 때문에 적어도 dp[n-i][k]보가 필요하다.우리는 항상 최악의 상황에 직면하여 i층에서 던진다. 우리는 max(dp[i-1][k-1], dp[n-i][k])+1보가 필요하기 때문에 추이 공식: dp[n][k]=min {max(dp[i-1][k-1], dp[n-i][k])+1}(1<=i<=n).

시간 복잡도 O(K*N^2)라는 문법은 본 문제에 적합하지 않다. 왜냐하면 이 문제의 N은 1e4.이기 때문이다.

int superEggDrop(int K, int N)
{
    int dp[N+2][K+2];
    for (int i = 0; i <= N; i++)
    {
        dp[i][0] = 0;
        dp[i][1] = i;
    }
    for (int j = 2; j <= K; j++)
    {
        for (int i = 1; i <= N; i++) 
        {
            dp[i][j] = i;   //     dp[i][j]           ，               。
            for (int k = 1; k < i; k++) 
            {
                dp[i][j] = min(dp[i][j], max(dp[k-1][j-1], dp[i-k][j]) + 1);
            }
        }
    }
    return dp[N][K];
}