【動态規劃】最長上升子序列LIS

經典問題

給一個長度為n的序列a，問其中最長上升子序列的長度為多少

O ( n 2 ) O(n^2) O(n2)做法

dp[i]:以a[i]結尾的最長上升子序列長度是多少

代碼：

int n;
int a[maxn],dp[maxn];
int ans[maxn];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
	}
	dp[0]=0;
	for(int i=1;i<=n;i++){
        for(int j=0;j<=i-1;j++){
            if(a[i]>a[j]){
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
	}
	for(int i=1;i<=n;i++) {
        cout<<dp[i]<<endl;
	}
    return 0;
}
           

O ( n l o g n ) O(nlogn) O(nlogn)做法

dp[i]:長度為i的最長公共子序列的最後一位最小可以是多少

這裡先給出 O ( n 2 ) O(n^2) O(n2)寫法：

int n;
int a[maxn],dp[maxn];
int ans[maxn];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
	}
	memset(dp,inf,sizeof(dp));
	dp[0]=0;
	for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(dp[j-1]==inf) break;
            if(dp[j-1]<a[i]){
                ans[i]=max(ans[i],j);
                dp[j]=min(dp[j],a[i]);
            }
        }
	}
	for(int i=1;i<=n;i++) {
        cout<<ans[i]<<endl;
	}
    return 0;
}
           

O ( n l o g n ) O(nlogn) O(nlogn)寫法

分析：

1. 在這種轉移下，我們不難發現dp數組是單調遞增的

2. 通過觀察和推導，我們會發現其實有很多轉移是多餘的，說白了我們隻需要找到比a[i]大于或等于的第一個數，然後替換掉就好了，相應的後面的都會被改上來

   代碼：

int n;
int a[maxn],dp[maxn];
int ans[maxn];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
	}
	memset(dp,inf,sizeof(dp));
	dp[0]=0;
	for(int i=1;i<=n;i++){
        int p=lower_bound(dp+1,dp+1+n,a[i])-dp;//如果是最長非遞減，隻需要把lower_bound改成upper_bound即可
        dp[p]=a[i];
        ans[i]=p;
	}
	for(int i=1;i<=n;i++) {
        cout<<ans[i]<<endl;
	}
    return 0;
}