สมมติว่าเราให้ไข่ K และเรามีอาคารที่มีชั้น N ตั้งแต่ 1 ถึง N ตอนนี้ไข่แต่ละฟองมีหน้าที่เหมือนกัน และถ้าไข่แตก เราจะไม่ทิ้งมันอีก
มีชั้น F ที่มีค่าระหว่าง 0 ถึง N โดยที่ไข่ที่ตกที่ชั้นที่สูงกว่า F จะแตก และไข่ที่ตกที่หรือต่ำกว่าชั้น F จะไม่แตก ในแต่ละการเคลื่อนไหว เราอาจเอาไข่หนึ่งฟองแล้ววางจากชั้น X ใดก็ได้ X อยู่ในช่วง 1 ถึง N
เป้าหมายของเราคือต้องรู้ว่าค่า F คืออะไร ดังนั้นจำนวนการเคลื่อนไหวขั้นต่ำที่เราจำเป็นต้องรู้อย่างมั่นใจว่า F คืออะไรโดยไม่คำนึงถึงค่าเริ่มต้นของ F จะเป็นเท่าใด
ดังนั้น หากอินพุตเป็น K =2 และ N =6 เอาต์พุตจะเป็น 3
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดอาร์เรย์ 2 มิติหนึ่ง 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 :=สร้างอาร์เรย์ 2 มิติ (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
