选取子问题x[i,j] 将其min(i<=k<=j) m[i,k-1]+m[k+1,j] + w[i,j] 加w[i,j] 是因为 引入根节点，和左右孩子节点的深度+1

w[i,j] 是 概率之和 就是 元素的概率和+缝隙的概率和

base情况

m[i,i-1] = 0 m是平均比较次数

目的：我们期望找到一个最小的平均比较次数。

所以我们希望 某树的平均比较次数 = 左子树的比较次数+右子树的比较次数 + 变化的概率（深度信息的变化） 我们需要改变根节点，来寻找最小。

时间复杂度分析：O（n^3） 构成： i,j的时间复杂度 O（n^2） 然后 min找最小 O（n） 因此总的是相乘

空间复杂度分析： 一个二维表nxn 所以 O（n^2）

采用迭代方法：（备忘录法）

for i in range(n):
    for j in range(i,n):

对于动态规划的总结：

1.划分子问题

2.找出递推关系和初值

3.是否满足优化原则

4.是否考虑标记函数

5.采用自底向上，用备忘录记忆