最大子矩陣和其實(shí)是最大子段和問(wèn)題的二維推廣.即給定一個(gè)m行n列的矩陣,求其一個(gè)子矩陣,行數(shù)從r1~r2,列數(shù)從c1~c2,使之全部元素之和為最大.
我們可以將最大子段和的動(dòng)態(tài)規(guī)劃解法推廣到上述二維情況.其基本思路為,若始行i1與末行i2已給定,則求以i1起始以i2結(jié)束的最大子矩陣之和,即等于一個(gè)一維的最大子段和問(wèn)題,只不過(guò)這里的數(shù)組a中元素a[j]是第j列里從第i1行加到第i2行的所有元素之和. 令t[i1,i2]表示這個(gè)行從i1到i2的最大子矩陣和,則求全矩陣的最大子矩陣之和的問(wèn)題就等于在1<=i1<=i2<=m的范圍中使t[i1,i2]最大化.
顯然上述算法的時(shí)間復(fù)雜度為O(m^2*n). 然而,容易看出,整個(gè)問(wèn)題的解決本質(zhì)上還是一個(gè)一維最大子段和的問(wèn)題,而在另一個(gè)維度--行上面,則還是枚舉所有的1<=i1<=i2<=m用打擂的方法比較出最大者.也就是說(shuō),此方法仍然只是在列這個(gè)維度上用到了動(dòng)態(tài)規(guī)劃.
有沒(méi)有可能對(duì)兩個(gè)維度進(jìn)行聯(lián)合的動(dòng)態(tài)規(guī)劃求解呢?
posted on 2007-03-23 15:18
w2001 閱讀(3899)
評(píng)論(3) 編輯 收藏 引用 所屬分類:
算法設(shè)計(jì)