[PKU暑課筆記] 動态規劃（二） 最長上升子序列 POJ1458最長公共子序列

五●例題

●最長上升子序列

1、子問題：求以ak（k=1, 2, 3…N）為終點的最長上升子序列的長度（一個上升子序列中最右邊的那個數，稱為該子序列的 “終點”）

2、确定狀态：子問題隻和一個變量--數字的位置相關。

是以序列中數的位置k就是“狀态”，而狀态 k 對應的“值”，就是以ak 做為“終點”的最長上升子序列的長度。

狀态一共有N個。

3、狀态轉移方程：

maxLen (1) = 1【初始狀态】

maxLen (k) = max { maxLen (i)：1<=i < k 且 ai < ak且 k≠1 } + 1【若找不到這樣的i，則maxLen(k) = 1】

maxLen(k)的值，就是在ak左邊，“終點”數值小于ak ，且長度最大的那個上升子序列的長度再加1。

因為ak左邊任何“終點”小于ak的子序列，加上ak後就能形成一個更長的上升子序列。

“人人為我”遞推型動歸程式

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN=1010;
int a[MAXN];
int maxlen[MAXN];

int main()
{
    int n;
    cin>>n;
    for(int i=1; i<=n; ++i)
    {
        cin>>a[i];
        maxlen[i]=1;
    }
    for(int i=2; i<=n; ++i)
        for(int j=1; j<i; ++j)
        {
            if(a[i]>a[j])
                maxlen[i]=max(maxlen[i],maxlen[j]+1);
        }
    cout<<*max_element(maxlen+1,maxlen+n+1);
    return 0;
}
           

“我為人人”遞推型動歸程式

/*#include<iostream> #include<cstring> #include<algorithm> using namespace std; const int MAXN=1010; int a[MAXN]; int maxlen[MAXN]; int main() { int n; cin>>n; for(int i=1; i<=n; ++i) { cin>>a[i]; maxlen[i]=1; }*/ for(int i=1; i<=n; ++i) for(int j=i+1; j<=n; ++j)//看看能更新哪些狀态的值 { if(a[j]>a[i]) maxlen[j]=max(maxlen[j],maxlen[i]+1); } /*cout<<*max_element(maxlen+1,maxlen+n+1); return 0; }*/

           

進一步，區分動規的3種形式

1)記憶遞歸型

優點：隻經過有用的狀态，沒有浪費。遞推型會檢視一些沒用的狀态，有浪費

缺點：可能會因遞歸層數太深導緻爆棧，函數調用帶來額外時間開銷。無法使用滾動數組節省空間。總體來說，比遞推型慢。

==>人人為我

==>我為人人

2)“人人為我”遞推型：狀态i的值Fi由若幹個值已知的狀态值Fk ,Fm ,..Fy推出，如求和，取最大值

在選取最優備選狀态的值Fm,Fn,…Fy時，有可能有好的算法或資料結構可以用來顯著降低時間複雜度。

3)“我為人人”遞推型：狀态i的值Fi在被更新（不一定是最終求出）的時候，

依據Fi去更新（不一定是最終求出）和狀态i相關的其他一些狀态的值Fk ,Fm ,..Fy

沒有什麼明顯的優勢，有時比較符合思考的習慣。個别特殊題目中會比“人人為我”型節省空間。

●一個補充：min_element()、max_element()和nth_element()

頭檔案：#include<algorithm>

作用：傳回容器中最小值和最大值。max_element(first,end,cmp);//其中cmp為可選擇參數？？？

#include<iostream>  
#include<algorithm>  
using namespace std;  
bool cmp(int a,int b)  
{  
      return a<b;  
}  
int main()  
{  
      int num[]={2,3,1,6,4,5};  
      cout<<"最小值是 "<<*min_element(num,num+6)<<endl;  
      cout<<"最大值是 "<<*max_element(num,num+6)<<endl;  
      cout<<"最小值是 "<<*min_element(num,num+6,cmp)<<endl;  
      cout<<"最大值是 "<<*max_element(num,num+6,cmp)<<endl;  
      return 0;   
}
           

●POJ1458 Common Subsequence 最長公共子序列 http://poj.org/problem?id=1458

輸入兩個串s1,s2,

設MaxLen(i,j)：s1的左邊i個字元形成的子串，與s2左邊的j個字元形成的子串的最長公共子序列的長度（i,j從0開始算）

MaxLen(i,j) 就是本題的“狀态”

假定 len1 = strlen(s1),len2 = strlen(s2)，那麼題目就是要求 MaxLen(len1,len2)

顯然，

MaxLen(n,0) = 0 ( n=0…len1）

MaxLen(0,n) = 0 ( n=0…len2）

遞推公式：

if ( s1[i-1] == s2[j-1] ) //s1的最左邊字元是s1[0]

MaxLen(i,j) = MaxLen(i-1,j-1) + 1;

else

MaxLen(i,j) = Max(MaxLen(i,j-1),MaxLen(i-1,j) );

【時間複雜度O(mn)】

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

char s1[1000];
char s2[1000];
int maxlen[1000][1000];

int main()
{
    while(cin>>s1>>s2)
    {
        int len1=strlen(s1);
        int len2=strlen(s2);
        int ntmp;
        for(int i=0;i<=len1;i++)
            maxlen[i][0]=0;
        for(int j=0;j<=len2;j++)
            maxlen[0][j]=0;
        for(int i=1;i<=len1;i++)
            for(int j=1;j<=len2;j++)
        {
            if(s1[i-1]==s2[j-1])//
                maxlen[i][j]=maxlen[i-1][j-1]+1;
            else maxlen[i][j]=max(maxlen[i][j-1],maxlen[i-1][j]);
        }
        cout<<maxlen[len1][len2]<<endl;
    }
    return 0;
}