首先弄清楚中序遍历是什么意思.
中序遍历是一个序列 (list).
不存在的节点的中序遍历是空序 ([]).
以 u 为根的二叉树的中序遍历 = u 的左儿子的中序遍历 + u + u 的右儿子的中序遍历
其中加号就是连接两个序列的意思.
题目里说只考虑叶子节点的中序遍历, 就是把所有非叶子从中序里扔掉就好了.
然后考虑从随便一个序列构造一个满足条件的二叉树. 其实这个二叉树上的任意一个点会对应原序列中的连续一段, 而这个点的值就是这一段的所有数的最大值.
我们考虑自底向上的建树. 也就是说最开始是 n 个单独的点, 然后每次建一个新点, 它的两个儿子分别是原来的两个点. 然后用这个新点代替原来的两个点. 重复 “挑选, 替代” 的过程直到只剩一个点, 就建成了一棵完整的树.
每次挑选的两个点一定代表原数组上相邻的两个区间. 合并后建成这棵树的 最小 代价为 左儿子的最小代价 + 右儿子的最小代价 + 左边最大值 * 右边最大值. 而我们的最小化目标是根的 最小 代价.
自然想到用 f[l][i] 代表以 i 为第一个数的长度为 l 的区间所代表的点为根的树 的 最小 代价. 首先 f[1][i] == a[i], 而我们的目标是 f[n][0].
进一步想, 最小化 f[l][i] 就是在所有该点的左右儿子分配方式 (就是各有多长, 总之加起来是 l) 中挑一个最小的. 也就是说 f[l][i] = min(f[j][i] + f[l - j][i + j] + max(a[i:i+j]) * max(a[i+j:i+l]) ) for j in [1, l).
那么直接使用这个式子把整个 f 数组递推出来就行.
btw 这是经典的区间合并动态规划. 其中 f[l][i] 是状态, 那个式子是状态转移方程.
可以参考一道2004年的经典题目 “合并果子”.