作者ponwar87123 (干我屁事喔北七)
看板Grad-ProbAsk
标题[理工] matrix-multiplication递回列式
时间Tue Jan 21 22:07:32 2020
https://imgur.com/ecy1Mt3
这题该怎麽列递回式子？
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 101.9.172.153 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1579615655.A.D43.html
1F：→ DLHZ: m[i,j]= min(m[i,k]+m[k+1,j]+p(i-1)pkpj), k=i~j-1, pi-1, 01/21 22:16
2F：→ DLHZ: pi个别为第i个矩阵的row数, column数 01/21 22:16
3F：→ DLHZ: 另外m[i,j]=0 if i=j 然後m[i,j]是第i个矩阵乘到第j个矩阵的 01/21 22:18
4F：→ DLHZ: 最小cost 01/21 22:18
5F：→ gash55025502: 照演算法的方式列的话 第二小题有办法解吗？ 01/21 22:27
6F：推 bochengchen: 想请问这是哪年的考题 01/21 22:29
7F：推 gash55025502: 我觉得第一小题答案应该是An=A1An-1+A2An-2+...+An- 01/21 22:33
8F：→ gash55025502: 1A1 01/21 22:33
9F：→ gash55025502: 第二小题应该是Catalan number调整一项或两项？ 01/21 22:33
10F：推 Aa841018: 台科104数学 01/21 22:33
11F：→ gash55025502: 他是在算矩阵乘法有几种相乘的方法 01/21 22:34
12F：→ cossetannie: 那应该就是算有几种括号的括法吧 01/21 22:37
13F：推 Aa841018: 欸g大好像是对的，这题该不会和108台科一样吧？https:// 01/21 22:38
14F：→ Aa841018: i.imgur.com/CSKoBhu.jpg 01/21 22:38
15F：→ DLHZ: 没看以为是DP的东西== 那应该是Catalan number 01/21 22:39
我知道是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
16F：→ DLHZ: (2n取n)/(n+1) 01/22 18:31
17F：→ DLHZ: 或是(2n取n) - (2n取(n+1)) 01/22 18:32
18F：推 mistel: k个矩阵的相异相乘数 n要代k-1 01/22 18:54
19F：→ mistel: 不过他应该是问递回 可能不能写成简式？ 01/22 18:54