前言

先分享一篇文章《動態規劃：從新手到專家》，作者正是通過這篇文章來學習的。文中對動態規劃的設計思想做了非常詳細的介紹，并通過簡單問題和復雜問題對動態規劃的設計流程進行剖析，以下是作者和出處：

• 作者：Hawstein

• 出處：http://hawstein.com/posts/dp-novice-to-advanced.html

問題描述

先介紹下問題，給定長度為N的整數序列：A[1], A[2], ......, A[N]，求得其中最長非降子序列的長度，即LIS(longest increasing subsequence)。比如如下的整數序列：

5, 3, 4,?8,?6, 7

其最大非降子序列即為3, 4, 6, 7，長度為4。

動態規劃求解

那么如何用動態規劃來求解這個問題呢？動態規劃中最重要的一部分就是定義狀態轉移方程，在這個問題中，如果我們定義d[i]為序列A[1], A[2], ..., A[i]的最長非降子序列，但很可惜，在后面思考中，我發現，d[i]和d[i-1]之間很難建立起狀態轉移關系，A[1]~A[i-1]和A[1]~A[i]二者的最長非降子序列間不一定有公共的部分，如1, 4, 2, 5, 3中前四個整數和前五個整數的最大非降子序列不一定有共同的部分，無法建立起狀態轉移關系。但如果用d[i]表示以元素A[i]結束的最長非降子序列的長度，那狀態方程就有規律可循了，我們以上面的序列為例：

d(1) = max{1}; //只有5

d(2) = max{1}; //3之前沒有比3小的

d(3) = max{1, d(2) + 1} = 2; //4之前有3

d(4) = max{1, d(2) + 1, d(3) + 1} = 3; //8之前有3, 4

d(5) = max{1, d(2) + 1, d(3) + 1} = 3; //6之前有3, 4

d(6) = max{1, d(2) + 1, d(3) + 1, d(5) + 1} = 4; //7之前有3, 4, 6

LIS = max(d[i]) = 4, 1 <= i < = 6

從上面的流程來看，先求出這個序列中以每個元素作為結尾的最大非降子序列的長度，那問題的解總是以序列中某個元素作為結尾的，所以取最大值即可。而且從上面的公式我們很容易看出求d[i]的過程，簡單來說，就是從i往前找，如果某個元素A[j] < = A[i]，那么以元素A[j]結尾的最長非降子序列再加上A[i]一定也是一個非降子序列，d[j] + 1肯定是一個非降子序列長度，找到所有符合條件的j，所有符合條件的d[j] + 1的最大值就一定是d[i]的值。從另一個角度去看，因為以A[i]為結尾的最長子序列的倒數第二個元素（假設長度不小于2）肯定是A[i]之前的某一個元素，所有A[j]作為倒數第二個元素的序列就是以A[i]為結尾的子序列。當然，還要考慮特殊的情況，假設A[i]之前沒有比其更小的元素，則子序列就是其本身，長度為1。綜上所述，狀態轉移方程如下：

d[i] = max(1, max(d[j] + 1)), 1 <= j < i, A[j] <= A[i];

最后問題的解即為：

LIS = max(d[i]); 1 <= i <= n, n為序列的長度

文章最后，貼上代碼：

#include <iostream> using namespace std;int LIS(int data[], int n) {int *d = new int[n];int len = 1;for(int i = 0; i < n; i++){d[i] = 1;for(int j = 0; j < i; j++){if(data[j] <= data[i]){if(d[j] + 1 > d[i]){d[i] = d[j] + 1;}}}if(d[i]>len) len = d[i];}return len; }int main() {int data[] = {1, 2, 3, 4, 5, 0};cout << LIS(data, 6) << endl;return 0; }

總結

以上是生活随笔為你收集整理的动态规划——最长非降子序列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。