|
先看题目：
你?前有?栋从 1 到 N 共 N 层的楼，然后给你 K 个鸡蛋 （ K ?少为 1）。现在确定这栋楼存在楼层 0 <= F <= N ，在这层楼将鸡 蛋扔下去，鸡蛋恰好没摔碎（?于 F 的楼层都会碎，低于 F 的楼层都不 会碎）。现在问你，最坏情况下，你?少要扔?次鸡蛋，才能确定这个楼层 F 呢？
?
那么具体如何解决问题在扔鸡蛋初阶版已经给出：（https://blog.csdn.net/m0_46591995/article/details/118660350）
那么今天解决的问题只有一个，那就是如何降低时间空间复杂度：如初阶版所说，降低复杂度的方法是先消除重叠子问题，没错，消除完子问题就已经可以较快速度的得出100以内的答案，但是算法复杂度仍然是指数级的。我们先看之前的代码片段：
int memo[max1][max1];
int dp1(int N,int K)//N为鸡蛋数目，K为楼层
{
if(N==1) return K;
if(K==0) return 0;
int res = max1;
if(memo[N][K]!=-1) return memo[N][K];
for(int i = 1 ; i <= K ; i++)//！！！！
{
int temp;
temp = max(dp1(N-1,i-1),dp1(N,K-i))+1;
res = min(res,temp);
}
memo[N][K]=res;
return res;
}
这边可以发现一个奇妙的地方，就是这个“for(int i = 1 ; i <= K ; i++)”的意义何在：
? ? ?
暴?穷举尝试在所有楼层 1 <= i <= N 扔鸡蛋，每次选择尝试次数最少
的那?层
；
那么意思也就是说我们在暴力枚举查找。
这样大家就能想到如何解决算法时间复杂度过大的问题了！
问题在于暴力枚举。。。那么查找算法中，最方便最快的查找算法是什么？ 答：二分法查找
那么问题就清晰了：我们采用二分法来查找出符合实际问题的 i。
至于不熟悉具体二分法的实现各位铁铁们去翻翻大二上学期《数据结构与算法》这本必修考试课的书，里面将会有比我更为专业熟练的解释，这边之间给出算法实现：
int dp(int N,int K)//N为鸡蛋数目，K为楼层 运用二分法搜索优化
{
if(N==1) return K;
if(K==0) return 0;
int res = max1;
if(memo[N][K]!=-1) return memo[N][K];
//for(int i = 1 ; i <= K ; i++)
//{
// int temp;
// temp = max(dp(N-1,i-1),dp(N,K-i))+1;
// res = min(res,temp);
//}
int low = 1,high = K;
while(low<=high)
{
int mid = (low+high)/2;
int broken = dp(N-1,mid-1);//鸡蛋碎了
int not_broken = dp(N,K-mid);//鸡蛋没碎
if(broken > not_broken)//寻找碎与没碎哪一个跟大
{
high = mid-1;
res = min(res,broken+1);
}
else{
low = mid+1;
res = min(res,not_broken+1);
}
}
memo[N][K]=res;
return res;
}
|