[理工] matrix-multiplication递回列式 ponwar87123 PTT批踢踢实业坊

楼主: ponwar87123 (干我屁事喔北七) 2020-01-21 22:07:32

https://imgur.com/ecy1Mt3
这题该怎么列递回式子？

作者: DLHZ ( ) 2020-01-21 22:16:00

m[i,j]= min(m[i,k]+m[k+1,j]+p(i-1)pkpj), k=i~j-1, pi-1,pi个别为第i个矩阵的row数, column数另外m[i,j]=0 if i=j 然后m[i,j]是第i个矩阵乘到第j个矩阵的最小cost

作者: gash55025502 (白影弓) 2020-01-21 22:27:00

照算法的方式列的话第二小题有办法解吗？

作者: bochengchen (LFII) 2020-01-21 22:29:00

想请问这是哪年的考题

作者: gash55025502 (白影弓) 2020-01-21 22:33:00

我觉得第一小题答案应该是An=A1An-1+A2An-2+...+An-1A1第二小题应该是Catalan number调整一项或两项？

作者: Aa841018 (andrew) 2020-01-21 22:33:00

台科104数学

作者: gash55025502 (白影弓) 2020-01-21 22:34:00

他是在算矩阵乘法有几种相乘的方法

作者: cossetannie (paa) 2020-01-21 22:37:00

那应该就是算有几种括号的括法吧

作者: Aa841018 (andrew) 2020-01-21 22:38:00

欸g大好像是对的，这题该不会和108台科一样吧？https://i.imgur.com/CSKoBhu.jpg

作者: DLHZ ( ) 2020-01-21 22:39:00

没看以为是DP的东西== 那应该是Catalan number

作者: mistel (Mistel) 2020-01-22 18:54:00

k个矩阵的相异相乘数 n要代k-1不过他应该是问递回可能不能写成简式？

继续阅读