[理工] 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不過他應該是問遞迴可能不能寫成簡式？

繼續閱讀