题目描述

初始化 所有的都等于0，然后在f[i,j]区间的初始化为无限大,这样才能够寻找到最小值

样例

import math
n = int(input())
f = [[0] * (n+1) for _ in range(n+1)]
w = [0] + list(map(int, input().split()))
s = [0] * (n+1)
for i in range(1, n+1):
    s[i] = s[i-1]+w[i]
for len in range(2,n+1):
    for i in range(1,n-len+2):
        j = i+len-1
        f[i][j] = math.inf
        for k in range(i,j):
            f[i][j] = min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1])
print(f[1][n])

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla