→ zuchang: 你沒辦法證明他的下界 可能存在 只是沒人想到 01/30 12:53
→ zuchang: 就是在有跟沒有之間 沒找到而已 01/30 13:21
推 FRAXIS: matrix chain 有 O(n lg n) 法 01/31 12:01
推 FRAXIS: 這題我猜滿足 quadrangle inequality 所以可以 O(n^2) 01/31 12:09
http://i.imgur.com/seUdA9O.jpg
http://i.imgur.com/uuUzxGv.jpg
第23題
解答只有D
這題我是用類似matrix chain 的DP做的
但是這樣應該是O(n^3)
這題有n^2內的做法ㄇ
-----
Sent from JPTT on my Sony H9493.
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.14.137.229 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1580359729.A.777.html