丢棋子问题#IT人的升职加薪tips# _升职

丈夫欲遂平生志，一载寒窗一举汤。这篇文章主要讲述丢棋子问题#IT人的升职加薪tips#相关的知识，希望能为你提供帮助。
关注公众号【程序员学长】，回复【电子书】，免费获得上百本计算机经典书籍

1问题描述一座大楼有 n+1 层，地面算作第0层，最高的一层为第 n 层。已知棋子从第0层掉落肯定不会摔碎，从第 i 层掉落可能会摔碎，也可能不会摔碎。给定整数 n 作为楼层数，再给定整数 k 作为棋子数，返回如果想找到棋子不会摔碎的最高层数，即使在最差的情况下扔的最小次数。一次只能扔一个棋子。
示例
输入：10,1
输出：10
说明：因为只有1棵棋子，所以不得不从第1层开始一直试到第10层，在最差的情况下，即第10层是不会摔坏的最高层，最少也要扔10次
分析问题
首先，我们令 f(n,k) 表示n层楼，k个棋子，在最差的情况下扔的最小实验次数。
我们来考虑一枚棋子从第j层扔下去，它会发生两种状态，即碎了和没碎。

碎了，说明从第j层以上的层数扔下去必然还是碎的，所以可以忽略大于j的层数，此时只剩下了k-1枚棋子和j-1层楼，剩下的实验次数为f(j-1,k-1)。
没碎，说明第j层和第j层以下的层数扔下必定还不碎，所以可以忽略小于j的层数，此时还有k枚棋子（因为这一枚棋子没碎，所以还能用）和 n-j 层楼，剩下的实验次数为 f(n-j，k)。

文章图片
image-20211117220003485
这里有一些特殊情况需要考虑一下。

若 n=0 ,此时在地面，肯定不会摔碎，所以不需要做任何实验，故f=0
若 k=1 ，表示只有一个棋子，我们必须逐层去操作，最坏的情况，即第n层楼才会摔碎，此时需要n次实验，故f=n。

因为我们不知道从第j层扔下棋子会不会摔碎，而题目要求的是求最差的情况，即以上两种情况的最大值，并且j的取值是不确定的，它的取值范围为是[1, n]，因此，我们需要枚举所有的j，计算j的所有取值中对应次数最小的那一个，才能表示最少的实验次数。
我们可以使用递归来求解，下面我们来看一下代码实现过程。

import sys
class Solution(object):
def solve(self,n,k):
#特殊条件
if n==0:
return 0
if k==1:
return n

res=sys.maxsize
#j的范围是[1,n]
for j in range(1,n+1):
#求最差情况下的最小的实验次数
res = min(res, 1 + max(self.solve(j - 1, k - 1), self.solve(n - j, k)))

return res

该算法的时间复杂度是O(n！)，空间复杂度是O(1)。该算法的时间复杂度太高，我们来看一下如何进行优化。
优化这道题我们可以使用动态规划来求解。根据上面推导出的关系式可以知道，动态规划的转移方程为:
?dp[i] [j] = min (1 + max (dp[p-1] [j-1] , dp[i-p] [j] ) ) ，其中p的范围是[1,k]
??dp[i][j]?? 表示i层楼，j个棋子, 在最差情况下的最少实验次数。
下面我们来看一下代码实现。

import sys
class Solution(object):
def solve(self,n,k):

if n==0:
return 0
if k==1:
return n

dp=[[0] * (k+1) for _ in range(n+1)]
print(dp)

#其中dp[i][1] = i，dp[0][k] = 0
for i in range(1,n):
dp[i][1]=i

for i in range(1, n+1):
for j in range(2,k+1):
dp[i][j]=sys.maxsize
for p in range(1,i+1):
#转移方程
dp[i][j] = min(dp[i][j],1+max(dp[p-1][j-1],dp[i-p][j]))

return dp[n][k]

【丢棋子问题#IT人的升职加薪tips#】

该算法的时间复杂度是O(n^2 * k) ，空间复杂度是O(nk)。
终极解法这里我们使用反向思维来求解，题目是求n层楼，k个棋子在最坏的情况下最少需要扔多少次。现在我们将问题逆向化，看i个棋子扔j次，最多可以测多少层楼这个问题（含义是指每次仍的位置都是最优的并且在棋子肯定够用的情况下），这里用dp[i] [j]来表示。
下面我们考虑第i个棋子在最优的楼层扔下去，有两种情况发生。

碎了，那么上面就不需要测了，下面能测 dp[i-1] [j-1] 层。
没碎，那么下面就不需要测了，上面能测 dp[i] [j-1] 层。
第i个棋子扔掉的那一层也能测。

综上所述，考虑最差的情形（即i个棋子扔 j 次，最多可测的的楼层数），可以求出状态转移方程为：
?dp[i] [j] = dp[i-1] [j-1] + dp[i] [j-1] + 1

初始时：因为不管有多少个棋子，扔一次就只能测一层楼，所以dp[i] [1] =1。
最终答案：i 不超过k时候, 使得dp[i] [j] > = n的最小的j。

下面我们还可以有两个优化。

我们知道N层楼用二分的方式扔log2N+1次就能直接确定哪层楼是棋子不会摔碎的最高层数，所以当给定的棋子数大于logN+1时，我们就直接返回log2N+1。
由于状态转移方程为dp[i] [j] = dp[i-1] [j-1] + dp[i] [j-1] + 1 ，即dp[i] [j] 只和它左上面的元素 dp[i-1] [j-1]和它左边的元素 dp[i] [j-1]，所以我们可以压缩为一维，并且需要从右往左计算，如下图所示：

文章图片
image-20211117223633001
如图所示，我们这里用粉色来表示dp[i] [j] ，用黄色来表示dp[i] [j-1] 。在计算dp[j] 的时候，我们从右往左遍历，一开始dp[j] 处为黄色，存储的是上一次迭代的结果dp[i] [j-1] ,j-1处也为黄色，因此dp[j] = dp[j] + dp[j-1] + 1 就等价于 dp[i] [j] = dp[i] [j-1] + dp[i-1] [j-1] + 1。
下面我们来看一下代码的实现。

import sys
import math
class Solution(object):
def solve(self,n,k):

if n==0:
return 0
if k==1:
return n

#优化性质, 如果k充分大, 二分的扔即可
b = int(math.log2(n) + 1)
if k > = b:
return b

dp = [1] * (k+1)

res=1
while True:
res=res+1
for j in range(k,1,-1):
print(j)
dp[j] = dp[j] + dp[j-1] + 1

if dp[j] > =n:
return res

dp[1]=res