思路

区间DP, 枚举区间长度$L$, 左端点$l$和分界点$k$

算法设计

1. 状态定义: f[l][r]表示区间$[l,r]$的划分方案的最小值
2. 状态转移方程: f[l][r]=min(f[l][r], f[l][k]+f[k][r]+a[l]*a[k]*a[r])

python 区间DP(水数据)

from typing import List
class Solution:
    def main(self, n:int, a:List[int]):
        f=[[0 for _ in range(n+1)] for _ in range(n+1)]
        for L in range(3, n+1):
            l=0
            while l+L-1<n:
                r=l+L-1
                for k in range(l+1, r):
                    if not f[l][r]: f[l][r]=float('inf')
                    f[l][r]=min(f[l][r], f[l][k]+f[k][r]+a[l]*a[k]*a[r])
                l+=1
        print(f[0][n-1])


if __name__ == '__main__':
    n=int(input())
    a=list(map(int, input().split()))
    sol=Solution()
    sol.main(n, a)