赞
踩
定义鸡蛋的硬度为 k,则代表鸡蛋最高从 k 楼扔下来不会碎掉,现在给你 n 个硬度相同的鸡蛋,楼高为 m,问最坏情况下最少测多少次,可以测出鸡蛋的硬度。
输入
输入两个数字 n,m(1≤n≤32,1≤m<231),代表 n 个鸡蛋和 m 层楼。
输出
输出一行整数,代表最坏情况下最少测多少次可以测出鸡蛋的硬度。
这道题属于动态规划,所以
第一步就要进行状态定义,利用dp[n][m]来表示n个鸡蛋测m层楼最多可以测多少次。
追求一般情况,在第k层楼测的时候,有可能有两种情况,1是鸡蛋碎,2是鸡蛋不碎,因为是最多最少,所以接下来要测的应该是楼层数较多的那一部分。(如向上测需要测20次,向下次需要测10次,取最坏情况为20次的)右因为是最大最少, 我们需要在所有的k中找到一个最小值。
所以状态转移方程就出来的:
dp[i][j] = min( max(dp[i][k - 1], dp[i - 1][j - k]) ) + 1; ( 1<=k<=j
看一下时间复杂度为
O
(
n
2
m
)
O(n^2m)
O(n2m)和空间复杂度
O
(
m
n
)
O(mn)
O(mn), 时间复杂度显然是不合理的,这个时候需要转换一种思维了。
dp[n][m] = k; 即n个鸡蛋测m层楼的次数是k次,m越大,k也就越大,即m和k是正相关的。我们就可以对状态定义进行优化,将k和m交换位置,即:dp[n][k] 表示n个鸡蛋仍k次最多测多少层楼,此时的状态转移方程就是:
dp[i][k] = dp[i][k - 1] + dp[i - 1][k - 1] + 1;
这就变成了一道递推的题,我们只需找到第一个dp[n][k]大于等于m的k即可。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。