牛客 扔鸡蛋

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

题目描述

k个鸡蛋，h层楼，最少用多少次能找到哪一层楼摔下去鸡蛋会碎。

先来看简单的场景：

k = 1 首先，如果k=1，很简单，最坏情况下最少要尝试h次。即，最高能探索的层数=最少探索次数。

k = 2 再看k=2即只有两个鸡蛋的场景。设最少尝试次数为x，那么x+(x-1)+…+2+1=(x+1)*x/2为最高能探索的层数。

具体解释为：

第一次将鸡蛋在第x层放下，如果摔碎了，另一个鸡蛋从第1层开始尝试到第x-1层，一共尝试x次；如果没摔碎，继续将这个鸡蛋从第x+(x-1)层放下，如果摔碎，从第x+1层尝试到第x+(x-1)-1层，即一共x次尝试；如果没摔碎，继续将这个鸡蛋从第x+(x-1)+(x-2)层放下，….

那么当k>2的情况呢？

用动态规划方法求解，假设用j个鸡蛋做i次尝试最高能探索到第dp[i][j]层。当dp[i][j]>h时的i即为所求。

初始状态： dp[i][1] = i：用1个鸡蛋，有i次尝试机会，就能到第i层（因为每次都是往上尝试1层）。 dp[1][j] = 1：有j个鸡蛋，只给1次尝试机会，那么最多只能尝试到第1层。这里注意了，因为只有1次尝试机会，你有再多个鸡蛋也没用。

dp[i][j]: 现在初始状态确定了，来看看dp[i][j]怎么确定，也就是有j个鸡蛋做i次尝试，最高能探索到第几层？

假设我们知道有j-1个鸡蛋做i-1次尝试最高能到几层，那现在多了1个鸡蛋，可以多做1次尝试，那最高能到多少层呢？这第i个鸡蛋只能再做1次尝试，因此，只能在dp[i-1][j-1]+1层尝试。

如果这次尝试鸡蛋碎了，我们就找到在第dp[i-1][j-1]+1层鸡蛋会碎啦；
如果这次尝试鸡蛋没碎，那么还能再对j个鸡蛋做i-1次尝试，因此，还能再高dp[i-1][j]层。 

因此，dp[i][j] = dp[i-1][j-1] + 1 + dp[i-1][j]

于是，可以写出动态规划的代码：

k, h = [int(x) for x in input().split()]
dp = [1]*(k+1)
cnt = 1
while dp[k] < h:
    cnt += 1
    dp_i_1 = dp[:]
    dp[1] = cnt
    for j in range(2,k+1):
        dp[j] = dp_i_1[j-1] + dp_i_1[j] + 1
print(cnt)

优化一下，变成：

k, h = [int(x) for x in input().split()]
dp = [0] * (k+1)
cnt = 0
while dp[k] < h:
    for i in range(k,0,-1):
        dp[i] += dp[i-1] + 1
    cnt += 1
print(cnt)