最近看DP的題目比較多，感覺真是遞歸之後的又壹大神器啊。
題目是這樣的： /problem.php?pid=1139
最開始我的分析是這樣的：要確定壹個矩陣至少得4個元素，即4個角；或者起始坐標以及長度寬度。我們可以遍歷每個頂點以及每種邊長。
可是這樣的復雜度簡直是爆炸的。
直覺告訴我，只能用動態規劃了。
因為動態規劃可以把復雜的問題劃分成很小的部分。
其實找到子問題是解題思路裏面最重要的部分。
我們之前碰到的壹個問題是，求壹維數組裏面的最大和。感覺這裏可以用，又不知道怎麽用。
我們上面說到了，確定壹個子矩陣得至少4個元素，那假設我們已經知道了其中的兩個：
假設最優解在第j行和第i行之間，剩下的就是去確定兩個列了。
1，我們遍歷所有的 行 的組合情況，即第i行到第j行的所有情況。
2，然後對每個組合之間的兩行之間的元素求這壹列的值
3，對壹個壹維的和數組求最大和
4，對上述的最大和求最大值
在具體實現的時候，我們定住第i行不動，移動第j行，然後不斷的求兩行之間的每壹列的和（壓縮）。
然後在每次移動i的時候，我們清空儲存列的和的數組。
程序：