题解 | #丢棋子问题#

class Solution:
    def solve(self , n: int, k: int): # k个棋子进行了t次实验，可以验证的楼高
        if n < 1 or  k < 1: return 0
        if k == 1: return n # 只能从第一层逐层尝试
           
        # 二分，最差的情况
        import math
        b = math.log2(n) + 1
        if k >= b:
            return int(b) # 如果k充分大, 二分的扔即可
        
        # 初始化，j=1，扔一次只能验证一层
        dp = [1] * (k+1) # dp[i]:i个棋子可以验证的楼层数
        
        res = 1 # 最少也要扔1次
        while True:
            res += 1
            # dp[i]依赖左边和左上, 为了防止覆盖, 需要倒着计算
            for i in range(k, 1, -1):
                dp[i]=dp[i]+dp[i-1]+1
                if dp[i] >= n:
                    return res
            dp[1] = res