#可以把切割的过程看成二叉树分裂的过程，每种切割法对应一颗二叉树，二叉树的所有内部结点和 #为总开销。只要构造出所有的二叉树，就能找到最小开销。给定的例子测试可行。 #复杂度感觉有点高，具体多少我也分析不来。。。 class TreeNode(): def __init__(self,val): self.val=val self.left=None self.right=None class Solution(): def leastPay(self,length,array): trees=self.toTrees(array) least=length*(length-1)/2 for tree in trees: least=min(self.toPay(tree),least) return least #构造所有可能的二叉树 def toTrees(self,array): if len(array)==1: return [TreeNode(array[0])] trees=[] leftEs,rightEs=self.divideElements(array) for leftE,rightE in zip(leftEs,rightEs): for leftT in self.toTrees(leftE): for rightT in self.toTrees(rightE): root=TreeNode(sum(array)) root.left=leftT root.right=rightT trees+=[root] return trees #把当前剩余元素随机划分到左右两颗子树，返回所有可能的划分情况 def divideElements(self,array): if len(array)==2: leftEs=[[array[0]],[array[1]]] rightEs=[[array[1]],[array[0]]] return (leftEs,rightEs) leftEs=[] rightEs=[] for i in range(len(array)): tempLs,tempRs=self.divideElements(array[:i]+array[(i+1):]) for j in range(len(tempLs)): leftEs+=[tempLs[j]+[array[i]]] rightEs+=[tempRs[j]] leftEs+=[tempLs[j]] rightEs+=[tempRs[j]+[array[i]]] return (leftEs,rightEs) #计算每棵树对应的开销 def toPay(self,tree): if not tree.left and not tree.right: return 0 elif tree.left and tree.right: return tree.val+self.toPay(tree.left)+self.toPay(tree.right) else: return "ERROR"