問題：
求一個一維數組中最長遞增子序列的長度。
解法1：
很明顯用動態規劃的算法，選取下面的階段（這種選法極為常見），可使階段間的關系具有無後效性。
階段：在所有以元素k結尾的子數組中，選出其中的最長遞增子序列，k=1,2...n。
狀態：以元素k結尾的最長遞增子序列中只有一個最長的遞增子序列。
決策：決定元素k結尾的最長遞增子序列有k-1種獲取的途徑，前面以任何一個元素結尾的最長遞增子序列都可能成為其的一部分。
這樣的時間復雜度為O(n^2)，空間復雜度為O(n)
[cpp]
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 1003
int A[MAXN];
int dp[MAXN];
// 動態規劃思想O(n^2)
int main()
{
int n, i, j, k;
cin >> n;
for (i=1; i<=n; i++)
cin >> A[i];
dp[1] = 1;
// 有n個階段
for (i=2; i<=n; i++)
{
dp[i] = 1; // 每個階段只有1個狀態
// 每個狀態有i種決策,以得出以元素i結尾的最長遞歸子序列的長度
for (j=i-1; j>=0; j--)
{
if (A[i]>A[j])
dp[i] = max(dp[i], dp[j]+1);
}
}
int maximum = dp[1];
for (i=2; i<=n; i++)
maximum = max(maximum, dp[i]);
cout << maximum;
}
解法2：
動態規劃的時間復雜度一般與空間復雜度相同，因為決定下一個階段的所有條件我們已存儲到dp中，在處理過程中我們可以對已得到的這些條件進行處理來降低時間復雜度。而這裡時間復雜度竟比空間復雜度高了O(n)，說明還有可以繼續優化的空間。
我們可以統計前面所有階段的最長遞增子序列的長度，將長度相同的最長遞增子序列分到同一組中，並只記錄它們最大元素的最小值MaxV[長度值]，如果階段k的元素大於長度為i最長遞增子序列的這個最小值MaxV[i]，那麼階段k的最長遞增子序列的長度至少為i+1。
而我們發現統計出的MaxV數組具有很好的遞增關系（動態規劃都是用來解決最優化問題，我們總能通過優化關系對之前統計出的結果進行排序），即如果i<j，那麼有MaxV[i]<MaxV[j]，最後用二分查找法來階段k的元素在MaxV數組中的位置即可。
證明：反證法，假設當i<j<=k，有MaxV[i]>=MaxV[j]，那麼存在一個長度為i的遞增序列a1a2...ai，且ai是計算到階段k時所有長度為i的遞增序列中最大元素的最小值，以及長度為j的序列b1b2...bj且ai>=bj，由於i<j長度j的序列b1b2...bj包含一個子序列b1b2...bi，且bi<bj<=ai，即長度為i的遞增子序列最大元素的最小值不是ai，矛盾。
[cpp]
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 1003
int A[MAXN];
int MaxV[MAXN];
// 動態規劃算法O(nlogn)
int main()
{
int n, i, j, k;
cin >> n;
for (i=1; i<=n; i++)
cin >> A[i];
MaxV[1] = A[1];
int nmaxv = 1; // 目前找到的最長遞增子序列的長度
// 有n個階段，每個階段有1個狀態
for (i=2; i<=n; i++)
{
// 每個狀態有nmaxv種決策，以得出以元素i結尾的最長遞歸子序列的長度
int u = 1, v = nmaxv;
while (u<=v)
{
int mid = (u+v)>>1;
if (MaxV[mid] < A[i])
u = mid+1;
else
v = mid-1;
}
// 每個元素都會對數組MaxV中的某個元素產生影響
// 使用二分搜索確定其在第v+1個位置
nmaxv = max(nmaxv, v+1);
MaxV[v+1] = A[i];
}
cout << nmaxv;
}
作者：linyunzju
