暴搜 5/11
n = int(input())
stones = [0] + list(map(int, input().split()))
s = [0 for i in range(n + 1)]
for i in range(1, n + 1):
s[i] += s[i - 1] + stones[i]
import sys
sys.setrecursionlimit(10000)
def dfs(l, r):
if l == r:
return 0
ssum = 0x3f3f3f3f
for i in range(l, r):
ssum = min(ssum, dfs(l, i) + dfs(i + 1, r) + s[r] - s[l - 1])
return ssum
print(dfs(1, n))
记忆化搜索 ac
n = int(input())
f = [[0 for i in range(n + 1)] for i in range(n + 1)]
stones = [0] + list(map(int, input().split()))
s = [0 for i in range(n + 1)]
for i in range(1, n + 1):
s[i] += s[i - 1] + stones[i]
import sys
sys.setrecursionlimit(10000)
def dfs(l, r):
if l == r:
return 0
if not f[i][j] == 0:#如果l,r区间已经搜过,直接返回就行
return f[i][j]
f[i][j] = 0x3f3f3f3f
for i in range(l, r):
f[i][j] = min(f[i][j], dfs(l, i) + dfs(i + 1, r) + s[r] - s[l - 1])
return f[i][j]
print(dfs(1, n))
记忆化搜索简单吧,就只是在暴搜的基础上加了个判断而已