版本二
# coding=gbk """ 为了减少测试次数,从每个厂家抽样3部手机参加测试。 某次测试的塔高为1000层,如果我们总是采用最佳策略, 在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢? """ dp = [[0, 0, 0] for _ in range(1001)] # 0层需要测试0次 # 一个手机时测试i层的耐摔程度需要i次 for i in range(1, len(dp)): dp[i][0] = i # 无论几个手机,测试第一层只需要1个手机 dp[1][0], dp[1][1], dp[1][2] = 1, 1, 1 # dp[layer][pho_num]代表有pho_num个手机测试layer层最差运气下需要的最少次数 for pho_num in range(1, 3): for layer in range(2, 1001): dp[layer][pho_num] = dp[layer - 1][pho_num] + 1 # 法一:在上一层的基础上增加一次测试次数 for i in range(2, layer + 1): # 发二:直接跳到第i层测试,加上后续测试次数即为总次数 # dp[layer-1][pho_num-1]: 表示在第i层测试时手机碎了,剩余测试楼层数为layer-1,手机数量-1 # dp[layer-i][pho_num]:表示在第i层测试手机时手机未碎,剩余测试楼层数layer-i,手机数pho_num f2 = 1 + max(dp[i - 1][pho_num - 1], dp[layer - i][pho_num]) dp[layer][pho_num] = min(dp[layer][pho_num], f2) print(dp[1000][2])