DP动态规划--乡村邮局问题-Post Office（POJ-1160）python

DP–乡村邮局问题-Post Office

Sample Input
10 5
1 2 3 6 7 9 11 22 44 50

Sample Output
9

python 版本

def arrange(arr, k):
    n = len(arr)
    arr = [0] + arr
    w = [[0] * (n+1) for _ in range(n+1)]
    # print(w)
    dp = [[0] * (n+1) for _ in range(n+1)]
    for i in range(n+1):
        for j in range(i+1, n+1):
            # print(i, j)
            w[i][j] = w[i][j-1] + arr[j] - arr[(i+j)//2]
    for i in range(1, n+1):
        dp[i][1] = w[1][i]  #在1-i之间建立一个邮局时的最短距离
        dp[i][i] = 0

    for i in range(1, n+1):
        zz = min(k, i)
        for j in range(2, zz+1):
            dp[i][j] = float("inf")
            # print(i-1, j)
            for z in range(j,i):
                # print(k,k+1,j)
                dp[i][j] = min(dp[i][j], dp[z][j-1] + w[z+1][i])
    return dp[n][k]