動態規劃 2 ——一維狀態 非降子序列問題

接下來將分類討論動態規劃演算法題，根據狀態的維數分為一維、二維、多維，還有樹形動態規劃。在每一維類別中通過具體的演算法題來總結一些經典的動態規劃模型，主要是一維和二維。首先看一維狀態中的非降子序列問題。

非降子序列問題

問題描述：

在一個無序的序列中{a[0], a[1],...a[n] }中找到一個最長的序列滿足： a[i] <= a[j] 且(0<=i<j<k…<m<=n-1)，反過來就是最長下降子序列，本質是一樣的。

問題分析：

如果前i-1個數中用到 a[k]( a[k]<= a[i])構成了一個的最長的序列加上第i個數，就是前i個數中用到作為最後一個數的最長的序列了。同樣的 a[k]構成的最長的序列有要求前k-1個數中……，這樣問題就拆成子問題了，通過序列的下標來劃分階段，階段k對應狀態opt[k]為 a[0],a[1],...a[k]中以 a[k]為最後一個數的最長序列的長度。

從上面的分析可以看出這樣劃分問題滿足最優子結構，那滿足無後效性么？顯然對於第i個數時只考慮前i-1個數,顯然滿足無後效性，可以用動態規劃解。

狀態轉移方程：

最長非降子序列：opt[i]=max(opt[j])+1(0<=j<i且a[j]<=a[i])

最長下降子序列：opt[i]=max(opt[j])+1(0<=j<i且a[j]>a[i])

代碼實現：

for(int i = 1; i < n; ++i){

for(int j = i – 1; j >= 0; --j){

if(a[i] >= a[j] &&opt[j] >= opt[i])

opt[i] = opt[j] + 1;

}

if(opt[i] > ans) ans = opt[i];

}

例題

1 攔截導

【問題描述】

某國為了防禦敵國的導彈襲擊，發展出一種導彈攔截系統。但是這種導彈攔截系統有一個缺陷：雖然它的第一發炮彈能夠到達任意的高度，但是以後每一發炮彈都不能高於前一發的高度。某天，雷達捕捉到敵國的導彈來襲。由於該系統還在試用階段，所以只有一套系統，因此有可能不能攔截所有的導彈。

輸入導彈依次飛來的高度（雷達給出的高度數據是不大於30000的正整數），計算這套系統最多能攔截多少導彈，如果要攔截所有導彈最少要配備多少套這種導彈攔截系統。

【輸入文件】http://missile.in

單獨一行列出導彈依次飛來的高度。

【輸出文件】missile.out

兩行，分別是最多能攔截的導彈數，要攔截所有導彈最少要配備的系統數

【輸入樣例】

389 207 155 300 299 170 158 65

【輸出樣例】

6

2

【問題分析】

有經驗的選手不難看出這是一個求最長非升子序列問題，顯然標準演算法是動態規劃。

以導彈依次飛來的順序為階段，設計狀態opt[i]表示前i個導彈中攔截了導彈i可以攔截最多能攔截到的導彈的個數。

狀態轉移方程：

opt[i]=max(opt[j])+1 (h[i]>=h[j],0=<j<i) {h[i]存，第i個導彈的高度}

最大的opt[i]就是最終的解。

這隻解決了第一問，對於第二問最直觀的方法就是求完一次opt[i]後把剛才要打的導彈去掉，在求一次opt[i]直到打完所有的導彈，但這樣做就錯了。

不難舉出反例： 6 1 7 3 2

錯解： 6 3 2/1/7 正解：61/7 3 2

其實認真分析一下題就回發現：每一個導彈最終的結果都是要被打的，如果它後面有一個比它高的導彈，那打它的這個裝置無論如何也不能打那個導彈了，經過這麼一分析，這個問題便抽象成在已知序列里找最長上升序列的問題。

求最長上升序列和上面說的求最長非升序列是一樣的，這裡就不多說了。

複雜度：時間複雜度為O（N2），空間複雜度為O（N）。

#include<iostream>using namespace std;class Solution {public: Solution() { a = NULL; }; void readData() { cin >> length; a = new int[length]; for (int i = 0; i < length; i++) { cin >> a[i]; } }; int maxSubSequence(bool ascend) { // "ascend" indicates if ascending or not. int* opt = new int[length]; int max = 0; for (int i = 0; i < length; i++) { opt[i] = 1; for (int j = i - 1; j >= 0; j--) { if ((!((a[j] <= a[i]) ^ ascend)) && opt[i] < opt[j] + 1) { opt[i] = opt[j] + 1; } } if (max < opt[i]) { max = opt[i]; } } delete[] opt; return max; }; void solve() { readData(); int anslen = maxSubSequence(false); int anstime = maxSubSequence(true); cout << anslen << endl; cout << anstime << endl; } ~Solution() { if(a != NULL)delete[] a; };private: int* a; int length; int anslen; int anstime;};

2 合唱隊形

N位同學站成一排，音樂老師要請其中的(N-K)位同學出列，使得剩下的K位同學排成合唱隊形。

合唱隊形是指這樣的一種隊形：設K位同學從左到右依次編號為1，2…，K，他們的身高分別為T1，T2，…，TK， 則他們的身高滿足T1<...<Ti>Ti+1>…>TK(1<=i<=K)。

你的任務是，已知所有N位同學的身高，計算最少需要幾位同學出列，可以使得剩下的同學排成合唱隊形。

【輸入文件】

輸入文件http://chorus.in的第一行是一個整數N(2<=N<=100)，表示同學的總數。第一行有n個整數，用空格分隔，第i個整數Ti(130<=Ti<=230)是第i位同學的身高(厘米)。

【輸出文件】

輸出文件chorus.out包括一行，這一行只包含一個整數，就是最少需要幾位同學出列。

【樣例輸入】

8

186 186 150 200 160 130 197 220

【樣例輸出】

4

【數據規模】

對於50％的數據，保證有n<=20；

對於全部的數據，保證有n<=100。

【問題分析】

出列人數最少，也就是說留的人最多，也就是序列最長。

這樣分析就是典型的最長下降子序列問題。只要枚舉每一個人站中間時可以的到的最優解。顯然它就等於，包括他在內向左求最長上升子序列，向右求最長下降子序列。

我們看一下複雜度：

計算最長下降子序列的複雜度是O（N2），一共求N次，總複雜度是O（N3）。這樣的複雜度對於這個題的數據範圍來說是可以AC的。但有沒有更好的方法呢？

其實最長子序列只要一次就可以了。因為最長下降（上升）子序列不受中間人的影響。

只要用OPT1求一次最長上升子序列，OPT2求一次最長下降子序列。這樣答案就是N-max(opt1[i]+opt2[i]-1).

複雜度由O（N3）降到了O（N2）。

#include<iostream>#include<vector>using namespace std;class Solution{private: int N; int* heights; void readData(){ cin>>N; heights = new int[N]; for(int i = 0; i < N; ++i){ cin >> heights[i]; } }; void destroy(){ if(heights != NULL){ delete[] heights; } heights = NULL; }public: Solution(){ heights = NULL; } ~Solution(){ destroy(); } int solve(){ readData(); vector<int> opt1(N, 1); vector<int> opt2(N, 1); for(int i = 1; i < N; ++i){ for(int j = i - 1; j >= 0; --j){ if(heights[i] > heights[j] && opt1[j] >= opt1[i]){ opt1[i] = opt1[j] + 1 } } } for(int i = N - 2; i >= 0; --i){ for(int j = i + 1; j < N; ++j){ if(heights[i] > heights[j] && opt2[j] >= opt2[i]){ opt2[i] = opt2[j] + 1; } } } int result = 0; for(int i = 0; i < N; ++i){ result = max(opt1[i] + opt2[i], result); } result = result - 1; // 自己算了兩次，減去一次； return result; }}

3 Buy Low Buy Lower (buylow.pas/c/cpp) 來源: USACO 4-3-1

【問題描述】

「逢低吸納」是炒股的一條成功秘訣。如果你想成為一個成功的投資者，就要遵守這條秘訣:

"逢低吸納,越低越買"

這句話的意思是：每次你購買股票時的股價一定要比你上次購買時的股價低.按照這個規則購買股票的次數越多越好，看看你最多能按這個規則買幾次。

給定連續的N天中每天的股價。你可以在任何一天購買一次股票，但是購買時的股價一定要比你上次購買時的股價低。寫一個程序，求出最多能買幾次股票。

以下面這個表為例, 某幾天的股價是:

天數 1 2 3 4 5 6 7 8 9 10 11 12

股價 68 69 54 64 68 64 70 67 78 62 98 87

這個例子中, 聰明的投資者(按上面的定義)，如果每次買股票時的股價都比上一次買時低，那麼他最多能買4次股票。一種買法如下(可能有其他的買法):

天數 2 5 6 10

股價 69 68 64 62

【輸入文件】http://buylow.in

第1行: N (1 <= N <= 5000), 表示能買股票的天數。

第2行以下: N個正整數 (可能分多行) ，第i個正整數表示第i天的股價. 這些正整數大小不會超過longint(pascal)/long(c++).

【輸出文件】buylow.out

只有一行，輸出兩個整數：

能夠買進股票的天數長度達到這個值的股票購買方案數量

在計算解的數量的時候，如果兩個解所組成的字元串相同，那麼這樣的兩個解被認為是相同的（只能算做一個解）。因此，兩個不同的購買方案可能產生同一個字元串，這樣只能計算一次。

【輸入樣例】

12

68 69 54 64 68 64 70 67

78 62 98 87

【輸出樣例】

4 2

【問題分析】

從題目描述就可以看出這是最長下降子序列問題，於是求解第一問不是難事，以天數為階段，設計狀態opt[i] 表示前i天中要買第i天的股票所能得到的最大購買次數。

狀態轉移方程：5

opt[i]=max(opt[j])+1 (a[i]>=a[j],0=<j<i) {a[i]存第i天股價}

最大的opt[i]就是最終的解。

第二問呢，稍麻煩一點。

從問題的邊界出發考慮問題，當第一問求得一個最優解opt[i]=X時，

在1到N中如果還有另外一個opt[j]=x那麼選取J的這個方案肯定是成立的。

是不是統計所有的opt[j]=x 的個數就是解了呢？

顯然沒那麼簡單，因為選取Ｊ這天的股票構成的方案不見得＝１，看下面一個例子：

５　6 4　3　１ 2

方案一：５４３１

方案二：５４３２

方案三：６４３１

方案四：６４３２

x=4

也就是所雖然opt[5]=X 和opt[6]=X但個數只有兩個，而實際上應該有四個方案，但在仔細觀察發現，構成opt[5]=x 的這個方案中 opt[j]=x-1的方案數有兩個,opt[j]=x-2的有一個，opt[j]=x-3 的有一個……

顯然這是滿足低歸定義的設計函數F（i）表示前I張中用到第i張股票的方案數。

遞推式：

1 (i=0)

F(i)=

Sum(F(j)) (0<=j<=n,a[j]>a[i],opt[j]=opt[i]-1) {sum 代表求和}

答案=sum(F(j)) {0<j<=n,opt[j]=x}

複雜度：

求解第一問時間複雜度是O(N2),求解第二問如果用遞推或遞歸+記憶化時間複雜度仍為O（N2）但要是用赤裸裸的遞歸那就複雜多了……，因為那樣造成了好多不必要的計算。

你認為這樣做就解決了這道題目了么？還沒有，還要注意一些東西：

（1）如果有兩個方案中出現序列一樣，視為一個方案，要需要加一個數組next用next[i] 記錄和第i個數情況一樣（即：opt[i]=opt[j] 且 a[i]=a[j]）可看做一個方案的最近的位置。

遞推時j只要走到next[i]即可。

（2）為了方便操作可以將a[n+1]賦值為-maxlongint這樣可以認為第n+1個一定可以買，答案就是sum(F(n+1))。

（3）看數據規模顯然要用高精度。

#include <iostream>using namespace std;class Solution {public: Solution() { a = NULL; }; void readData() { cin >> N; a = new int[N + 2]; a[0] = INT_MAX; for (int i = 1; i <= N; i++) { cin >> a[i]; } a[N + 1] = INT_MIN; }; void solve(){ readData(); int* opt = new int[N + 2]; int* next = new int[N + 2]; int max = INT_MIN; for (int i = 0; i <= N + 1; i++) { opt[i] = 1; for (int j = i - 1; j >= 0; j--) { if (a[j] > a[i] && opt[i] < opt[j] + 1) opt[i] = opt[j] + 1; } if (max < opt[i]) max = opt[i]; } max = max - 2; for (int i = 1; i <= N + 1; i++) { int j = i - 1; for (; j > 0; j--) { if (opt[j] == opt[i] && a[j] == a[i]) { break; } } next[i] = j; } int* F = new int[N + 2]; F[0] = 1; for (int i = 1; i <= N+1; i++) { F[i] = 0; for (int j = i - 1; j >= next[i]; j--) { if (opt[i] == (opt[j] + 1) && a[j] > a[i]) { F[i] += F[j]; } } } cout << max << endl; cout << F[N+1]<< endl; delete[] F; delete[] opt; delete[] next; } ~Solution() { if(a != NULL) delete[] a; };private: int N; int* a;};

4 船 (ships.pas/c/cpp) 來源：《奧賽經典》（提高篇）

【問題描述】

PALMIA國家被一條河流分成南北兩岸，南北兩岸上各有N個村莊。北岸的每一個村莊有一個唯一的朋友在南岸，且他們的朋友村莊彼此不同。

每一對朋友村莊想要一條船來連接他們，他們向政府提出申請以獲得批准。由於河面上常常有霧，政府決定禁止船隻航線相交（如果相交，則很可能導致碰船）。

你的任務是編寫一個程序，幫助政府官員決定批准哪些船隻航線，使得不相交的航線數目最大。

【輸入文件】http://ships.in

輸入文件由幾組數據組成。每組數據的第一行有2個整數X，Y，中間有一個空格隔開，X代表PALMIA河的長度（10<=X<=6000），Y代表河的寬度（10<=Y<=100）。第二行包含整數N，表示分別坐落在南北兩岸上的村莊的數目（1<=N<=5000）。在接下來的N行中，每一行有兩個非負整數C，D，由一個空格隔開，分別表示這一對朋友村莊沿河岸與PALMIA河最西邊界的距離（C代表北岸的村莊，D代表南岸的村莊），不存在同岸又同位置的村莊。最後一組數據的下面僅有一行，是兩個0，也被一空格隔開。

【輸出文件】ships.out

對輸入文件的每一組數據，輸出文件應在連續的行中表示出最大可能滿足上述條件的航線的數目。

【輸入樣例】

30 4

7

22 4

2 6

10 3

15 12

9 8

17 17

4 2

0 0

【輸出樣例】

4

【問題分析】

這道題目相對來說思考難度較高，從字面意義上看不出問題的本質來，有點無法下手的感覺。這裡我給大家推薦兩種思考這類問題的方法。

法一：尋找規律法（我前面總結提到的第3個方法）

尋找規律自然要推幾組數據，首先當然有從樣例入手；

C1 C2 C3 C4

北岸紅線的端點： 4 9 15 17

南岸紅線的端點： 2 8 12 17

D1 D2 D3 D4

不難看出無論線的斜率如何，都有這樣的規律：

C1<C2<C3<C4 且 D1<D2<D3<D4

如果我們把輸入數據排升序，問題變抽象為：

在一個序列（D）里找到最長的序列滿足DI<DJ<Dk……且i<j<k

這樣的話便是典型的最長非降子序列問題了。。。。

法二：邊界條件法（我前面總結提到的第4個方法）

邊界法其實就是把數據往小了縮，顯然N=1是答案是1。N=2時呢？

考慮這樣一組數據：

N=2

C1 D1

C2 D2

當 C1<C2 時，如果D1>D2 那麼一定會相交，反之則不會相交。

當C1 >C2時，如果D1<D2 那麼一定會相交，反之則不會相交。

N=3

C1 D1

C2 D2

C3 D3

……

其實不用在推導N=3了，有興趣的可以推導去。看N=2時就能得出：

對於任意兩條航線如果滿足Ci<Cj 且Di<Dj 則兩條航線不相交。這樣的話要想在一個序列里讓所有的航線都不相交那比然滿足，C1<C2<C3…Cans且D1<D2<D3…<Dans ，也就是將C排序後求出最長的滿足這個條件的序列的長度就是解。

這樣分析後顯然是一個最長非降子序列問題。

複雜度：排序可以用O（nlogn）的演算法，求最長非降子序列時間複雜度是O(n2).

總複雜度為O（n2）.

#include<iostream>#include<algorithm>using namespace std;class Solution { private: pair<int,int> *data; int N; public: Solution(){ data = NULL; }; ~Solution(){ if(data != NULL) delete[] data; } static int cmp(pair<int,int> a, pair<int, int> b){ return a.first < b.first; }; void readData(){ cout<<"please input the number of village pairs:"; cin >> N; data = new pair<int, int>[N]; for(int i = 0; i < N; i++){ cin >> data[i].first >> data[i].second; } sort(data, data + (N-1), cmp); }; int solve(){ int* opt = new int[N]{0}; int max = 1; opt[0] = 1; for(int i = 1; i < N; i++){ for(int j = i - 1; j >= 0; j--){ if(data[i].second > data[j].second && opt[i] < opt[j] + 1){ opt[i] = opt[j] + 1; } } if (opt[i] > max){ max = opt[i]; } } return max; }};

推薦閱讀：