面试常考题之丢棋子问题

读前福利，送大家一些电子书

丢棋子问题

问题描述

一座大楼有 n+1 层，地面算作第0层，最高的一层为第 n 层。已知棋子从第0层掉落肯定不会摔碎，从第 i 层掉落可能会摔碎，也可能不会摔碎。给定整数 n 作为楼层数，再给定整数 k 作为棋子数，返回如果想找到棋子不会摔碎的最高层数，即使在最差的情况下扔的最小次数。一次只能扔一个棋子。

示例

输入：10,1

输出：10

说明：因为只有1棵棋子，所以不得不从第1层开始一直试到第10层，在最差的情况下，即第10层是不会摔坏的最高层，最少也要扔10次

分析问题

首先，我们令 f(n,k) 表示n层楼，k个棋子，在最差的情况下扔的最小实验次数。

我们来考虑一枚棋子从第j层扔下去，它会发生两种状态，即碎了和没碎。

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

这里有一些特殊情况需要考虑一下。

• 若 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]

该算法的时间复杂度是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

1. 初始时：因为不管有多少个棋子，扔一次就只能测一层楼，所以dp[i] [1] =1。

2. 最终答案：i 不超过k时候, 使得dp[i] [j] >= n的最小的j。

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

• 我们知道N层楼用二分的方式扔log₂N+1次就能直接确定哪层楼是棋子不会摔碎的最高层数，所以当给定的棋子数大于logN+1时，我们就直接返回log₂N+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]，所以我们可以压缩为一维，并且需要从右往左计算，如下图所示：

如图所示，我们这里用粉色来表示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

该算法的时间复杂度是O(klogN)，因为外层循环while最多迭代logn轮，否则可以直接使用二分扔棋子的方式来求解，能层循环是k次，所以总的时间复杂度是O(klogn)，空间复杂度是O(n)。