matrix chain multiplication dp# JobHunting - 待字闺中h*22013-12-24 08:121 楼matrix chain multiplication dp那道题有O(N^2)的解法吗?感觉这题和palindrome partition 2 那题比较像,但是怎么也想不出O(N^2)的解法平安夜做题的人飘过~~问下大家~~
h*22013-12-24 08:122 楼ding~【在 h*********2 的大作中提到】: matrix chain multiplication dp那道题有O(N^2)的解法吗?: 感觉这题和palindrome partition 2 那题比较像,但是怎么也想不出O(N^2)的解法: 平安夜做题的人飘过~~: 问下大家~~
A*c2013-12-24 08:123 楼我觉得matrix和palin 2的题目是不一样的的。matrix dp你要考虑所有的i,j下标组合,所以你要考虑n^2个子问题而palin 2你只要考虑所有的后缀就行了,子问题的数目是n个如果要说像,我觉得palin2和cutting rod有点像【在 h*********2 的大作中提到】: matrix chain multiplication dp那道题有O(N^2)的解法吗?: 感觉这题和palindrome partition 2 那题比较像,但是怎么也想不出O(N^2)的解法: 平安夜做题的人飘过~~: 问下大家~~