题解 | #质检员的烦恼#写了一天，还是时间复杂度太高，真的心累。求高手改！！！

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算质检员每轮应该如何选择正整数K，才能在运气最差的情况下用最短的时间找到不合格的手机？并输出该最短的时间。
# @param n int整型 手机个数N
# @param a int整型 单个移动时间A
# @param b int整型 单组称重时间B
# @return long长整型
#
import math
import itertools
class Solution:
    def minTime(self , n: int, a: int, b: int) -> int:
        # write code here
        dp = [0] * (n + 1)
        dp[1] = a + b  # 单个手机：移动+称重
        dp[2] = 2 * (a + b)

        for i in range(3, int((n+1)/2)+1):
            dp[i] = i*(a+b)
            precost = i * a
            for groups in range(2, int(i/2)+1):
                cost = precost + groups * b  # 当前轮次成本：移动+称重
                if cost > dp[i]:
                    continue
                # 最坏情况下的下一轮的组大小
                maxGroupSize = (i + groups - 1) // groups if i > groups else 0
                # 最坏情况下的下一轮成本，如果组大小小于i，则为dp[maxGroupSize]的值，否则为0
                nextMaxGroupCost = dp[maxGroupSize]
                totalCost = cost + nextMaxGroupCost  # 总成本：当前成本+最坏情况下的下一轮成本
                dp[i] = min(dp[i], totalCost)  # 更新最小成本

        precost = n * a
        dp[n]=n*(a+b)
        for groups in range(2, int((n+1)/2)+1):
                cost = precost + groups * b  # 当前轮次成本：移动+称重
                # 最坏情况下的下一轮的组大小
                maxGroupSize = (n + groups - 1) // groups if n > groups else 0
                # 最坏情况下的下一轮成本，如果组大小小于i，则为dp[maxGroupSize]的值，否则为0
                nextMaxGroupCost = dp[maxGroupSize]
                totalCost = cost + nextMaxGroupCost  # 总成本：当前成本+最坏情况下的下一轮成本
                dp[n] = min(dp[n], totalCost)  # 更新最小成本

        return dp[n]

已知如果求dp[100]的话，只需要求dp[50],不需要dp[99]那些，因为肯定最少也是对半分吧。但是代码实在不会改了，哪位高手改一下吧