[理工] matrix-multiplication遞迴列式

[ponwar87123 (干我屁事喔北七)]

https://imgur.com/ecy1Mt3

這題該怎麼列遞迴式子？

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.9.172.153 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1579615655.A.D43.html
→ DLHZ: m[i,j]= min(m[i,k]+m[k+1,j]+p(i-1)pkpj), k=i~j-1, pi-1,
→ DLHZ: pi個別為第i個矩陣的row數, column數
→ DLHZ: 另外m[i,j]=0 if i=j 然後m[i,j]是第i個矩陣乘到第j個矩陣的
→ DLHZ: 最小cost
→ gash55025502: 照演算法的方式列的話 第二小題有辦法解嗎？
推 bochengchen: 想請問這是哪年的考題
推 gash55025502: 我覺得第一小題答案應該是An=A1An-1+A2An-2+...+An-
→ gash55025502: 1A1
→ gash55025502: 第二小題應該是Catalan number調整一項或兩項？
推 Aa841018: 台科104數學
→ gash55025502: 他是在算矩陣乘法有幾種相乘的方法
→ cossetannie: 那應該就是算有幾種括號的括法吧
推 Aa841018: 欸g大好像是對的，這題該不會和108台科一樣吧？https://
→ Aa841018: i.imgur.com/CSKoBhu.jpg
→ DLHZ: 沒看以為是DP的東西== 那應該是Catalan number
我知道是catalan number
但遞迴式子沒想法＠＠
※ 編輯: ponwar87123 (101.9.172.153 臺灣), 01/22/2020 18:25:59
啊 查了一下108的答案 明白了
※ 編輯: ponwar87123 (101.9.172.153 臺灣), 01/22/2020 18:30:22
→ DLHZ: (2n取n)/(n+1)
→ DLHZ: 或是(2n取n) - (2n取(n+1))
推 mistel: k個矩陣的相異相乘數 n要代k-1
→ mistel: 不過他應該是問遞迴 可能不能寫成簡式？