→ tkcn:我的看法和你的結論相同 05/30 00:02
推 FTT:n個矩陣連乘的組合 可由排n-1組括號進去來表達 05/30 21:23
→ FTT:所以算Catalan number才會代n-1進去呀 05/30 21:23
我在讀Cormen的演算法(二版)
有一個地方不是很了解(在書上的333頁)
=====================================
解決 n 個矩陣的乘法
所有的括號是 P(n)
P(n) = 1 if n = 1
sum(k=1 to n-1) P(k)P(n-k) if n >= 2
如果是 4 個矩陣相乘
P(4)帶入這個遞迴式的結果是5
=> 四個矩陣有5種方法相乘
(A1(A2(A3A4)))
(A1((A2A3)A4))
((A1A2)(A3A4))
((A1(A2A3))A4)
(((A1A2)A3)A4)
然後Catalan number的公式 (2n)! / (n+1)!n!
這邊用n=4帶入會得到14
n=3會得到5
所以是要求n個矩陣相乘，在Catalan number要代n-1，在P(n)要代n嗎?
謝謝
=====================================
這是Catalan number 維基百科的介紹
http://zh.wikipedia.org/zh-tw/Catalan_number
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.228.30.220