leetcode887 鸡蛋掉落

思路1:

dp+二分。

实现1:

 1 class Solution
 2 {
 3 public:
 4     int superEggDrop(int k, int n)
 5     {
 6         vector> dp(k + 1, vector(n + 1, 0x1f3f3f3f));
 7         for (int i = 0; i <= k; i++)
 8         {
 9             for (int j = 0; j <= n; j++)
10             {
11                 if (i == 1 or i >= j) dp[i][j] = j;
12             }
13         }
14         for (int i = 1; i <= k; i++)
15         {
16             for (int j = 1; j <= n; j++)
17             {
18                 int l = 1, r = j - 1, ans = -1;
19                 while (l <= r)
20                 {
21                     int m = l + r >> 1;
22                     if (dp[i - 1][m - 1] <= dp[i][j - m])
23                     {
24                         ans = m; l = m + 1;
25                     }
26                     else r = m - 1;
27                 }
28                 if (ans != -1)
29                 {
30                     dp[i][j] = min(dp[i][j], 1 + max(dp[i - 1][ans - 1], dp[i][j - ans]));
31                     if (ans + 1 < j)
32                     {
33                         ans++;
34                         dp[i][j] = min(dp[i][j], 1 + max(dp[i - 1][ans - 1], dp[i][j - ans]));
35                     }
36                 }
37             }
38         }
39         return dp[k][n];
40     }
41 };

思路2:

逆向思维dp。dp[i][j]表示i次操作，j个鸡蛋最多能确定的楼层数。

实现2:

 1 class Solution {
 2 public:
 3     int superEggDrop(int k, int n) {
 4         vector>dp(n+1,vector(k+1,0));
 5         for(int i=1;i<=n;i++){
 6             dp[i][1]=i;
 7         }
 8         for(int i=1;i<=k;i++){
 9             dp[1][i]=1;
10         }
11         int res=n;
12         bool flg=false;
13         for(int i=2;i<=n;i++){
14             for(int j=2;j<=k;j++){
15                 dp[i][j]=1+dp[i-1][j-1]+dp[i-1][j];
16                 if(dp[i][j]>=n){
17                     flg=true;res=i;break;
18                 }
19             }
20             if(flg)break;
21         }
22         return res;
23         
24     }
25 };