题解 | 【模板】区间dp

def solve():
    # Read input
    n = int(input())

    # Handle special case when n=1
    if n == 1:
        print(0)
        return

    # Read array elements
    a = [0] + list(map(int, input().split()))

    # Calculate prefix sums
    sum_arr = [0] * (n + 1)
    for i in range(1, n + 1):
        sum_arr[i] = sum_arr[i - 1] + a[i]

    # Initialize dp array
    dp = [[0] * (n + 1) for _ in range(n + 1)]

    # Initialize base cases for adjacent pairs
    for i in range(1, n):
        dp[i][i + 1] = a[i] + a[i + 1]

    # Fill dp array
    for length in range(2, n):
        for left in range(1, n - length + 1):
            right = left + length
            min_cost = float("inf")

            # Try all possible splits between left and right
            for j in range(left, right):
                cost = dp[left][j] + dp[j + 1][right]
                min_cost = min(min_cost, cost)

            # Add the cost of combining all elements in the range
            dp[left][right] = min_cost + (sum_arr[right] - sum_arr[left - 1])

    # Print result
    print(dp[1][n])


solve()