给定 P=a1×a2×a3×……×an,依据乘法结合律,不改变其顺序,只用括号表示成对的乘积,试问有几种括号化的方案
n=4的例子如下
假设这个数是h(n-1), (这里之所以是n-1,是因为实际上n指的是元素个数,每2个元素乘一次,只要n-1次就可以乘完)
那么显然h(n-1)=h(0)h(n-2)+h(1)h(n-3)+...+h(n-2)h(0)
对应的例子则是
a(b(cd)) a((bc)d) h(0)h(n-2) (只要先对右边的n-2个元素进行乘积,接着再跟最左边的元素相乘,h(0)=1)
(ab)(cd) h(1)h(n-3) (先乘最左边的2个元素,再乘最右边的n-3个元素,之后再把这2个元素相乘)
(a(bc))d ((ab)c)d h(n-2)h(0)
从括号化展开的应用
1. 进出栈
对括号进行进出栈的模拟,左括号代表进栈,右括号代表进行出栈,那么进出栈的顺序就相当于括号化的方案
2.三角剖分
三角剖分就是从距阵乘法类比过来的,而距阵乘法就是括号化的问题