本文共 1436 字,大约阅读时间需要 4 分钟。
这道题记得以前在gym上训练欧洲区域赛做过,但是现在完全忘了.
很自然的想法就是用动态规划去求解.
首先想到的是定义dp[i][j]为i层楼,j个鸡蛋最少需要多少次求解,状态转移就是:
for(int x=2; x<=i-1; i++)
dp[i][j] = min( max(dp[x-1][j-1], dp[i-x-1][j]) ) + 1
但是这样需要枚举n*k*n, 主要是中间需要求一个最佳的分割位置,求一个最小值.导致多了个n的时间复杂度,肯定会超时.
上面这个循环是求最小值的,理论是可以用三分查找来代替,但是 这个函数存在很多的相等值,所以三分查找也会出错.
所以只能换一种思路dp,把dp状态换一下,现在是给定楼层n,球的数量k,要求最少多少次测试成功, 可以转换为给定测试数字i,球k,最多能测多少楼,也就是球dp[i][k]>=n的最小的i.
这样做的好处就是,我们在转移的时候可以忽略到底在哪个位置分割是最佳的,也就是省略之前做的那次循环.
现在求dp[i][j],j个球测试i次,最多能测多少楼, 假设我们在某个楼层x扔出鸡蛋,
1如果鸡蛋碎了,意味着我们要在1-(x-1)的位置继续测试,这时候只剩下i-1次测试机会和j-1个球,意味着我们最高只能在dp[i-1][j-1]+1的地方测试,因为再高,剩下来的测试机会和球测不出下面的楼层的f的值在哪了.
2如果鸡蛋没碎,意味值f的值是在x的上面,这个时候剩下i-1测测试机会和j个球,也就是在x上面最多再有dp[i-1][j]层,不然也测不出f值在哪了.
所以第一次测试只需要在dp[i-1][j-1]+1的地方把鸡蛋扔下去,那么不管鸡蛋碎还是不碎,都能测试出dp[i-1][j-1]+1+dp[i-1][j]层楼的f值.
所以转移方程式就是:
dp[i][j]=dp[i-1][j-1]+1+dp[i-1][j].
时间复杂度就变成了O(n*k).
class Solution {public: int dp[10005][105]; int superEggDrop(int k, int n) { for(int i=1; i<=1000; i++)dp[i][1]=i; for(int i=1; i<=100; i++)dp[1][i]=1; int ans=10000; for(int i=2; i<=200; i++){ for(int j=2; j<=k; j++){ dp[i][j]=dp[i-1][j]+dp[i-1][j-1]+1; // printf("%d %d %d\n", i, j, dp[i][j]); if(dp[i][j]>=n){ ans=i; break; } } if(ans!=10000)break; } if(k==1)return n; if(n==1)return 1; return ans; }};
转载地址:http://enywb.baihongyu.com/