题解 | 能量项链

区间dp

1）构建二维数组dp[n][n]，dp[i][j]代表以i为起点，j为终点的区间的最优解。

2）按照序列长度从1到n，起点从1到n-1的顺序二层循环

3）状态转移方程：dp[i][j] = max_j dp[i][k] + dp[k][j] + nums[i] * nums[k+1] * nums[j+1]

注意：遍历过程中，k，j，K+1，j+1均有可能超界，需要对n取余。

import sys

n = int(input())
nums = list(map(int, input().split()))
nums += nums
mod = 10**9 + 7

dp = [[(0, 0, 0)] * n for _ in range(n)]
for i in range(1, n+1):
    for j in range(n):
        k, l = j, j+i-1
        if i==1:
            dp[k][k] = (0, nums[k], nums[k+1])
        else:
            val = 0
            for ind in range(k, l):
                ind = ind - n if ind >= n else ind
                l = l - n if l >= n else l
                val1, head1, tail1 = dp[k][ind]
                val2, head2, tail2 = dp[0 if ind==n-1 else ind+1][l]

                assert tail1==head2
                new_val = val1 + val2 + head1*tail1*tail2
                if new_val > val:
                    val = new_val
            dp[k][l] = (val, nums[k], nums[l+1])
res = 0
for i in range(n):
    j = i+n-1 if i+n-1<n else i-1
    res =  max(res, dp[i][i-1][0])
print(res % mod)