赞
踩
N层楼,K个鸡蛋,找楼层 F ,满足高于 F 的楼层落下的鸡蛋都会碎,从 F 楼层或比它低的楼层落下的鸡蛋都不会破,问找到这个F需要测试的最小鸡蛋数目
dp的思路:找状态,做选择(max or min),穷举选择,思考base case
∴
本题状态就是鸡蛋数K和要判断的楼层数N,随着测试(状态变化)鸡蛋数会减少,楼层数会减少;
选择就是选择去哪一层(i)丢鸡蛋, 丢了鸡蛋后有两个结果:鸡蛋碎了,接下来要去i层往下测试了(k --> k-1, N—>i-1 );鸡蛋没碎,往i+1到N层去测试(k—>k, N—>N-i)
那状态转移方程就定了,用dp[鸡蛋数][楼层数]或者dp(鸡蛋数, 楼层数)表示状态转移,外加一个for循环遍历所有的选择,以此择优更新结果
res = min(res, max(dp(k-1, i-1), dp(k, N-i))+1)
base case 体现在代码上就是最开始做的一些判断(我觉得), 当N= =0,不需要测试返回0, 当K==1,那就只能从第一层开始往上测试,最坏情况就只能是返回N
拿一个鸡蛋去某一层楼扔,关于要选择去哪一层扔,我们不知道,那就把楼层都试一遍,至于鸡蛋碎没碎,下一次怎么选择,就不用去操心,因为有正确的状态转移,递归会算出每个选择的代码,我们取最优的就是最优的
class Solution { public: int dp(int K, int N, vector<vector<int>>& memo) { //base case if(K==1) return N; if(N==0) return 0; if(memo[K][N] != -1) return memo[K][N]; int res = INT_MAX; for(int i = 1; i<N+1; i++)//选择在第i层开始,范围是i到N+1 {//(碎了,没碎)+1 res = min(res, max(dp(K-1, i-1,memo), dp(K, N-i, memo))+1); //+1表示在第i层楼扔了一次 } memo[K][N] = res; return res; } int superEggDrop(int K, int N) { //要有一个备忘录,是二维数组,注意数组的大小, vector<vector<int>> memo(K+1, vector<int>(N+1, -1)); return dp(K, N, memo); } };
随着N的增大,不管算法策略有多好,测试次数总是呈现增加趋势的,那么两个状态选择dp(K-1, i-1)
和dp(K, N-i)
固定K和N,随着i的增加,前者会单调递增,后者会单调递减,要求这两个选择的较大值再求这些较大值中的最小值(图来自力扣官方解析),就是两条线的交点。
那就用二分查找来优化线性搜索的复杂度,
由于与上面的线性查找楼层没有本质区别,所有空间复杂度与时间复杂度打败率都不高,但是没有超过时间限制了,就先这样吧==
class Solution { public: int dp(int K, int N, vector<vector<int>>&memo) { if(K == 1) return N; if(N == 0) return 0; if(memo[K][N] != -1) return memo[K][N]; int res = INT_MAX; int low = 1, high = N; int mid = 0; int broken = 0, not_broken = 0; while(low <= high)//二分找楼层 { mid =(low+high)/2; broken = dp(K-1, mid-1, memo);//碎了, 需要测试的次数 not_broken = dp(K, N- mid, memo);//没碎情况需要的测试第二个参数始终表示还有多少层楼待测试 //取两种情况下的较大值们的最小值 if(broken > not_broken) { high = mid-1; res = min(res, broken+1); }else{ low = mid+1; res = min(res, not_broken+1); } } memo[K][N] = res; return res; } int superEggDrop(int K, int N) { vector<vector<int>> memo(K+1, vector<int>(N+1, -1)); return dp(K, N, memo); } };
放个官方解答, 没有本质区别,就是参考一下map的备忘录
//官方解答,用map做备忘录,将K和N放一起作为key,也蛮不错,但本质都是一样的 class Solution { unordered_map<int, int> memo;//用map做备忘录 int dp(int K, int N) { if (memo.find(N * 100 + K) == memo.end()) { int ans; if (N == 0) ans = 0; else if (K == 1) ans = N; else { int lo = 1, hi = N;//就是用二分代替线性查找 while (lo + 1 < hi) { int x = (lo + hi) / 2; int t1 = dp(K-1, x-1); int t2 = dp(K, N-x); if (t1 < t2) lo = x; else if (t1 > t2) hi = x; else lo = hi = x; } ans = 1 + min(max(dp(K-1, lo-1), dp(K, N-lo)), max(dp(K-1, hi-1), dp(K, N-hi))); } memo[N * 100 + K] = ans; } return memo[N * 100 + K]; } public: int superEggDrop(int K, int N) { return dp(K, N); } };
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。