以1,3,5,7,9,11,12,13,15为树叶权重，画出最优二叉树，并求出权重
根据最优二叉树的构建思路，我们可以使用动态规划的方法来解决。
首先，我们将树叶权重按照从小到大的顺序排列如下：
1 3 5 7 9 11 12 13 15
接下来，我们定义一个二维数组dp，其中dp[l][r]表示从第l个叶子节点到第r个叶子节点构成的最优二叉树的权重和。初始值为0。
然后，我们需要确定状态转移方程，即如何更新dp数组的值。假设我们现在要计算dp[l][r]，可以枚举所有可能的根节点k，将dp[l][r]更新为以下所有情况中的最小值：
dp[l][r] = min(dp[l][r], dp[l][k-1] + dp[k+1][r] + weight_sum(l, r))
其中，weight_sum(l, r)表示从第l个叶子节点到第r个叶子节点的权重和，可以通过前缀和预处理得到。
下面是具体的计算过程：
初始化dp数组，所有元素初始化为0
dp[l][r] = 0 for l in range(n) for r in range(n)
计算叶子节点的权重和，并存储在一个前缀和数组中
prefix_sum = [0]
for w in weights:
prefix_sum.append(prefix_sum[-1] + w)
枚举区间长度，从小到大枚举所有可能的区间，更新dp数组
for length in range(1, n+1):
for l in range(n-length+1):
r = l + length - 1
for k in range(l, r+1):
dp[l][r] = min(dp[l][r], dp[l][k-1] + dp[k+1][r] + prefix_sum[r+1] - prefix_sum[l])
最终的最优二叉树权重和为dp[0][n-1]
下面是最终的代码实现：
weights = [1, 3, 5, 7, 9, 11, 12, 13, 15]
n = len(weights)
# 初始化dp数组
dp = [[0]*n for _ in range(n)]
# 计算前缀和
prefix_sum = [0]
for w in weights:
prefix_sum.append(prefix_sum[-1] + w)
# 计算dp数组
for length in range(1, n+1):
for l in range(n-length+1):
r = l + length - 1
dp[l][r] = float('inf')
for k in range(l, r+1):
dp[l][r] = min(dp[l][r], dp[l][k-1] + dp[k+1][r] + prefix_sum[r+1] - prefix_sum[l])
# 最终答案为dp[0][n-1]
print("最优二叉树的权重和为：", dp[0][n-1])
运行结果为 最优二叉树的权重和为： 140，因此最优二叉树的权重和为140。