此题网上可以搜索到的解法是:令dp[k][n]表示用k个鸡蛋来测试n层楼,需要用的最少的trial次数.这种定义是和题意一致的.动态转移方程是:
dp[k][n] = min_i {max(dp[k-1][i-1],dp[k][n-i])+1} for i =1,2,...,n (+1是因为0 index)
基本思想是我们考虑将一个蛋放在第i层去实验.如果碎了,那么我们只能继续尝试dp[k-1][i-1];如果没有碎,那么我们相当于可以继续用k个蛋去尝试第i层以上共N-i层楼的实验.但这种遍历n的循环非常耗时,因为n可以非常大.
另一种巧妙的解法是改变状态的定义,令dp[k][m]表示用k个鸡蛋和m次尝试,最多可以测试的楼层的高度.那么转移方程是:
dp[k][m] = dp[k-1][m-1]+dp[k][m-1]+1
这个思想是,我们设x=dp[k-1][m-1],那么我们在第x+1层扔一个鸡蛋:如果碎了,我们就用(k-1,m-1)的策略,能测量的楼层仍然是x.如果没碎,我们就能在x+1层之上,用(k,m-1)的策略,再检测x2 = dp[k][m-1]层楼.所以总的来说,高度在x1+1+x2之内的楼层,我们必然都可以通过(k,m)来实现检测.