摔手机蓝桥 Python

dp = [[0, 0, 0, 0] for _ in range(1001)] # 只有一个手机时测试n楼层时需要的测试次数 for i in range(1, 1001): dp[i][1] = i # 无论多少个手机 第一层所需要的测试次数永远是1 for i in range(len(dp[1])): dp[1][i] = 1 # print(dp[1][1], dp[1][2], dp[1][3]) # print(dp) # ind 还需要测试的楼层数量 cnt: 手机数量 for cnt in range(2, 4): # 第二部手机 第三部手机 # 只有一个手机时要测试ind个楼层所需要的 次数 -> 两个手机时要测试ind个楼层所需要的 次数 # 两 个手机时要测试ind个楼层所需要的 次数 -> 三 个手机时要测试ind个楼层所需要的 次数 for ind in range(2, 1001): # 从第一层到第1000层 # 第ind层cnt个手机需要的测试次数 = 第ind - 1层cnt个手机需要的测试次数 + 1 dp[ind][cnt] = dp[ind - 1][cnt] + 1 for k in range(2, ind + 1): # 寻找第k层 使得第k层摔手机是测试ind层需要的 最少次数 # 跳至第k层需要 1次 跳至k层之后最坏的情况需要的次数 max(dp[k-1][cnt-1], dp[ind-k][cnt]) # max(dp[k-1][cnt-1], dp[ind-k][cnt]) 表示取差的情况（需要的测试次数最多） # min表示采取这两种策略中测试次数最小的 dp[ind][cnt] = min(dp[ind][cnt], 1 + max(dp[k-1][cnt-1], dp[ind-k][cnt])) # ind-k会出现等于0的情况 0层需要的测试次数为0 生成数组时已定义 # dp[k-1][cnt-1]: 在第k层测试坏了 楼层数测试范围缩小至[1, k-1] 剩余手机数量[cnt-1] # dp[ind-k][cnt]: 在第k层测试没坏 楼层数测试范围缩小至[K+1, ind] 剩余手机数量[cnt] # print(f'层数 {ind} 手机数量 {cnt} 需要测试次数：', dp[ind][cnt]) print(dp[1000][3])

版本二

# 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])