APCS 2024.01 m934. 4. 合併成本

        要計算最小合併成本，就需要用到DP，DP的精髓就是分而治之，假設今天只有3個資料要合併，-1,3,-5，那麼情形不外乎是(-1,(3,-5) ) 或是 ((-1, 3),-5)，從兩個之中找最小成本。如果這時候再增加一個資料如-1,3,-5,6那麼情形就是((-1,3,-5),6)或是((-1,3),(-5,6))或是(-1,(3,-5,6))之中找最小成本，我們可以發現，只要每次切割區間的左右邊界，直到找到1.左右邊界相同，代表沒有合併成本，2.左右邊界差一，那就是相鄰兩個合併，可以直接運算，3.這個左右邊界夾出來的最小成本已經算過，直接回傳資料。

        以下附上完整程式碼：

def check(left , right):
    if dp[left][right] != 9999999:
        return dp[left][right]
    if left == right: return 0
    elif left == right-1:
        return abs(d[left] - d[right])
    mm = 9999999
    for i in range(left , right):
        l,r = check(left , i) , check(i+1 , right)
        dp[left][right] = min(dp[left][right],abs((table[i+1] - table[left]) - (table[right+1] - table[i+1]))  + l+r)
        mm = min(mm,dp[left][right])
    return mm
        

n = int(input())
d = [int(i) for i in input().split()]
dp = [[9999999 for i in range(n)] for j in range(n)]
table = [0]
for i in d:
    table.append(table[-1] + i)

print(check(0,n-1))