<p>如果你能将暴力组织成记忆化,那么暴力也没那么糟糕</p>
<p>该方法可以递归地进行左右分割,以确定最佳解决方案,将每个左侧前缀与最佳解决方案相结合,从而减少右侧分割的次数。由于这将多次计算同一个右侧拆分,因此内存化(将过去的结果保留在内存中以供重用)将使大多数探索分支短路</p>
<pre><code>from functools import lru_cache
from itertools import accumulate
def minMaxSum(A,x):
@lru_cache() # memoization for
def findBest(start,splits): # best split from start position to end of A
R = A[start:] # right-side/remaining elements
# base cases (no recursion)
if splits == 1: return max(R),[R]
if splits == len(R): return sum(R),[[r] for r in R]
# progressively increasing size of left side subarray
bestSum = sum(R)+1
maxLeft = 0
for i,r in enumerate(R[:len(R)-splits+1],1):
if r >= bestSum: break # won't improve on best at this point
maxLeft = max(maxLeft,r) # max for left side
subSum,subArrays = findBest(start+i,splits-1) # recurse right side
subSum += maxLeft
if subSum>=bestSum: continue # track improvement to best solution
bestSum = subSum
bestSplit = [R[:i],*subArrays] # left side + best right side solution
return bestSum,bestSplit
# convert to break indexes and return solution
maxSum,subArrays = findBest(0,x)
breaks = list(accumulate(map(len,subArrays)))[:-1]
return breaks,maxSum,subArrays
</code></pre>
<p>输出:</p>
<pre><code>print(*minMaxSum([10,30,40,20,50],2))
# [1] 60 [[10], [30, 40, 20, 50]]
print(*minMaxSum([10,30,40,20,50],3))
# [1, 2] 90 [[10], [30], [40, 20, 50]]
print(*minMaxSum([40,30,40,20,50],3))
# [3, 4] 110 [[40, 30, 40], [20], [50]]
print(*minMaxSum([40,25,30,45,40,20,35,50],5))
# [1, 2, 5, 6] 180 [[40], [25], [30, 45, 40], [20], [35, 50]]
A = [i%5+1 for i in range(37)]
x = 11
print(*minMaxSum(A,x))
# [1, 2, 5, 6, 7, 10, 11, 12, 35, 36] 27
# [[1], [2], [3, 4, 5], [1], [2], [3, 4, 5], [1], [2],
# [3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5], [1], [2]]
</code></pre>