携帯電話ブルーブリッジ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])

バージョン2

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