题目

Leetcode 887. 鸡蛋掉落

代码（9.25 首刷看解析）

class Solution {
public:unordered_map<int, int> memo;int superEggDrop(int K, int N) {return dp(K, N);}int dp(int k, int n) {int ans;if(!memo.count(n*100+k)) {if(n == 0) {ans = 0;} else if(k == 1) {ans = n;} else {int l = 1, r = n;while(l+1 < r) {int mid = (l+r)/2;int t1 = dp(k-1, mid-1);    // 碎了int t2 = dp(k, n-mid);  // 没碎if(t1 < t2) {l = mid;} else if(t1 > t2) {r = mid;} else {l = r = mid;}}ans = 1 + min(max(dp(k-1, l-1), dp(k, n-l)),max(dp(k-1, r-1), dp(k, n-r)));}memo[n*100+k] = ans;}return memo[n*100+k];}
};