K 개의 알을 줬고 1에서 N까지의 N 층을 가진 건물이 있다고 가정합니다. 이제 각 달걀은 기능이 동일하며 달걀이 깨지면 다시 떨어뜨릴 수 없습니다.
0과 N 사이에 F층이 존재하여 F보다 높은 층에 떨어진 계란은 깨지고 F층 이하에 떨어진 계란은 깨지지 않습니다. 각 이동에서 우리는 X 층에서 계란 하나를 가져와서 떨어뜨릴 수 있습니다. X는 1에서 N까지의 범위에 있습니다.
우리의 목표는 F의 값이 무엇인지 확실히 아는 것입니다. 그렇다면 F의 초기 값에 관계없이 F가 무엇인지 확실히 알아야 하는 최소 이동 횟수는 얼마입니까?
따라서 입력이 K =2 및 N =6과 같으면 출력은 3이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
하나의 2D 배열 dp 정의
-
solve() 함수를 정의하면 K, N,
가 필요합니다. -
N <=1이면 -
-
반환 N
-
-
K가 1과 같으면 -
-
반환 N
-
-
dp[K, N]이 -1과 같지 않으면 -
-
반환 dp[K, N]
-
-
ret :=N, 낮음 :=0, 높음 :=N
-
낮음 <=높음, 수행 -
-
왼쪽 :=1 + 해결(K - 1, 중간 - 1)
-
오른쪽 :=1 + 해결(K, N - 중간)
-
ret :=ret의 최소값과 왼쪽과 오른쪽의 최대값
-
왼쪽이 오른쪽과 같으면 -
-
루프에서 나오세요
-
-
왼쪽 <오른쪽이면:
-
낮음 :=중간 + 1
-
-
그렇지 않으면 높음 :=중간 - 1
-
-
반환 dp[K, N] =ret
-
주요 방법에서 다음을 수행하십시오 -
-
dp :=하나의 2D 배열 생성 (K + 1) x (N + 1), -1로 채움
-
해결 반환(K, N)
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<vector<int>> dp;
int solve(int K, int N) {
if (N <= 1)
return N;
if (K == 1)
return N;
if (dp[K][N] != -1)
return dp[K][N];
int ret = N;
int low = 0;
int high = N;
while (low <= high) {
int mid = low + (high - low) / 2;
int left = 1 + solve(K - 1, mid - 1);
int right = 1 + solve(K, N - mid);
ret = min(ret, max(left, right));
if (left == right)
break;
if (left < right) {
low = mid + 1;
} else
high = mid - 1;
}
return dp[K][N] = ret;
}
int superEggDrop(int K, int N) {
dp = vector<vector<int>>(K + 1, vector<int>(N + 1, -1));
return solve(K, N);
}
};
main(){
Solution ob;
cout << (ob.superEggDrop(2,6));
} 입력
2, 6
출력
3