题解 | #打气球的最大分数#递归TLE
打气球的最大分数
https://www.nowcoder.com/practice/35119064d0224c35ab1ab612bffee8df
import sys
n = int(input().strip())
arr = [1] + list(map(int, input().strip().split())) + [1]
# TODO: dp
def recur(l, r):
if l == r:
return arr[l-1] * arr[l] * arr[r+1]
ret = max(arr[l-1] * arr[l] * arr[r+1] + recur(l+1, r), arr[l-1] * arr[r] * arr[r+1] + recur(l, r-1))
for i in range(l+1, r):
ret = max(ret, arr[l-1] * arr[i] * arr[r+1] + recur(l, i-1) + recur(i+1, r))
return ret
print(recur(1, n))
查看11道真题和解析