資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 超級雞蛋掉落問題
假設我們有 K 個雞蛋，並且有一棟有 N 層樓的建築物，樓層從 1 到 N。現在每個雞蛋的功能都相同，如果一個雞蛋碎了，我們就不能再掉它了。
存在一個樓層 F，其範圍在 0 到 N 之間，任何在 F 以上樓層掉落的雞蛋都會碎，而任何在 F 或 F 以下樓層掉落的雞蛋都不會碎。在每次移動中，我們都可以取一個雞蛋，並從任何樓層 X 掉落它。X 的範圍在 1 到 N 之間。
我們的目標是確定地知道 F 的值是多少。那麼，無論 F 的初始值是多少，我們都需要多少次最少的移動才能確定地知道 F 的值？
因此，如果輸入類似於 K = 2 和 N = 6，則輸出將為 3。
為了解決這個問題，我們將遵循以下步驟：
定義一個二維陣列 dp
定義一個函式 solve()，它將接收 K、N 作為引數。
如果 N <= 1，則：
返回 N
如果 K 等於 1，則：
返回 N
如果 dp[K, N] 不等於 -1，則：
返回 dp[K, N]
ret := N，low := 0，high := N
當 low <= high 時，執行：
left := 1 + solve(K - 1, mid - 1)
right := 1 + solve(K, N - mid)
ret := ret 和 left 與 right 中的最大值之間的最小值
如果 left 等於 right，則：
退出迴圈
如果 left < right，則
low := mid + 1
否則 high := mid - 1
返回 dp[K, N] = ret
從主方法執行以下操作：
dp := 建立一個 (K + 1) x (N + 1) 的二維陣列，並將其填充為 -1
返回 solve(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
更新於: 2020年6月4日
389 次瀏覽
廣告