只要有順序關係，就可以輕巧地將題目分切成子問題，並且將子問題的狀態單純地收整起來，提升計算效率！我們來討論兩個相關的例子。

平面上雙調旅行售貨員問題 Euclidean Bitonic Traveling Salesman Problem

我們在若干天以前提及過，旅行售貨員問題其實是個 NP-完備問題。就算是在平面上的旅行售貨員問題也都是 NP-完備的（不過平面上的旅行售貨員問題有著比較良好的近似演算法）。一個經典的演算法習題是這樣的：給定平面上 N 個點的座標，能否從最左邊的點出發，經過所有點恰好一次再回到最左邊的點。使得這條路現的 x-座標是先遞增再遞減的？

解題思考

首先我們可以將所有點的座標由左至右排列為 v1, v2, ..., vn。接著，對於所有 i < j，定義 dp(i, j) 為從 v1 開出兩條單調向右的路線，一條連到 i、另一條連到 j。並且經過所有 v1,..., vj 之間的頂點。經過觀察，我們可以發現當 i < j-1 的時候，顯然 vj-1 這個點必須要跟著 vj 在同一條路徑上的（否則就不能一路向右了）。在此情形下有 dp(i, j) = dp(i, j-1) + dist(vj-1, vj)。在 i = j-1 的情形下，我們可以枚舉 vj 的前一個點：它可能是 v1, v2, ..., vj-2 的任何一個（但不會是 vi，因為大家都用 vscode了會黏在一起變成一個圈就不是兩條路徑了）。於是，我們有 dp(i, j) = min{ dp(k, i) + dist(vk, vj) : 1 ≤ k ≤ j-2}。

我們來看看另一個在平面上有著單調性的問題吧！

平面上最大空矩形問題

給你平面上 N 個點，請找出一個座標平行於座標軸的矩形，並且它四個邊界上至少貼齊一個點。使得該矩形面積最大。

解題思考

這題是離散化變成加權最大子矩形的一個應用。我們可以把所有節點和邊界切成一格一格的，每一格都有一個權重（等於面積、或 -inf 如果這個地方不可能形成矩形）。然後就可以用最大子矩形的方法來解囉。不過這樣是 O(n^3)，如果需要變快的話，還是直接掃描線比較好～

平面上最大內空凸多邊形

讓我們來考慮上面矩形問題的延伸。如果我們想要找出面積最大的、以輸入的點為頂點的凸多邊形，但是內部不能有其他點，該怎麼找呢？

解題思考

我們可以考慮 dp(low, i, j)，表示 low 這個點為「凸多邊形最低點」，然後沿著逆時針方向拉出一個凸多邊形，然後最後兩個點是 vi 跟 vj 的時候，最大的凸多邊形面積為何。轉移就變得很單純了，我們要找的是 vk 使得 vi → vj → vk 是向右轉，並且加上這 low vi vj 這三個點形成的三角形面積即可！時間複雜度是 O(n^4)。