最長遞增子序列

輸入一個整數(shù)數(shù)組S[n]，計算其最長遞增子序列的長度，及其最長遞增子序列。

算法一：L[k]

定義$k(1\le k\le n)$，L[k]表示以 S[k] 結(jié)尾的遞增子序列的最大長度。子問題即為 L[k]。
對于每一個k，我們都遍歷前面0~k-1的所有的數(shù)，找出最大的L[i]，且$S[k]>L[i]$，此時$L[k]=L[j]+1$。不斷地維護當(dāng)前的最大的遞增子序列的長度。

轉(zhuǎn)移方程：

時間復(fù)雜度： 填表過程從1~n遍歷一次 $O(n)$，在填L[k]時遍歷了一次L[1…k-1] $O(n)$。因此時間復(fù)雜度：$$T(n)=O(n^2)$$
空間復(fù)雜度： 創(chuàng)建了備忘錄L[n]，因此空間復(fù)雜度: $$S(n)=O(n)$$

代碼：文章來源地址http://www.zghlxwxcb.cn/news/detail-772283.html

int lis_dp1(const vector<int>& s, int n) {
    vector<int> Lis(s.size(),-1);
    int ans=1;
    for(int i=1;i<=n;i++){
        int cnt=1;
        for(int j=i-1;j>0;j--){
            if(s[i]>s[j]) cnt=max(cnt, Lis[j]+1);
        }
        Lis[i]=cnt;
        ans=max(ans, Lis[i]);
    }
    return ans;
}

算法一：L[k]的改進，求最長遞增子序列

思路： 基于算法一得到最終的L，同時在填表過程中不斷維護出現(xiàn)最長遞增子序列的元素的下標(biāo)index。i從下標(biāo)index-1開始，不斷往前遍歷，當(dāng)$s[i]<s[index]\&\&L[i]+1==L[index]$時，S[i]即為最長遞增子序列的元素。

時間復(fù)雜度： 基于算法一進行改進，原時間復(fù)雜度$O(n^2)$。但沒有進行循環(huán)的再嵌套，只是在外層增加了一個while循環(huán)用于找到最長遞增子序列，時間復(fù)雜度為$O(n)$。因此總的時間復(fù)雜度為：$$T(n)=O(n^2)$$

空間復(fù)雜度： 基于算法一進行改進，原空間復(fù)雜度$O(n)$。只新創(chuàng)建了一個一維數(shù)組，空間復(fù)雜度為$O(n)$。因此總的空間復(fù)雜度度為：$$S(n)=O(n)$$

代碼：

vector<int> find_lis_dp1(const vector<int>& s, int n) {
    vector<int> Lis(s.size(),-1), L;
    int ans=1,index;
    for(int i=1;i<=n;i++){
        int cnt=1;
        for(int j=i-1;j>0;j--){
            if(s[i]>s[j]) cnt=max(cnt, Lis[j]+1);
        }
        Lis[i]=cnt;
        if(ans<Lis[i]){
            ans=Lis[i];
            index=i;
        }
    }
    L.push_back(s[index]);ans--;
    for(int i=index-1;ans>0;i--){
        if(s[i]<s[index]&&Lis[i]+1==Lis[index]){
            L.push_back(s[i]);
            ans--;
            index=i;
        }
    }
    reverse(L.begin(), L.end());
    return L;
}

算法二：L[i][j]

定義i和j ($1\le i\le j\le n$)，L(i, j)表示$S[j...n]$中所有元素均大于$S[i]$的最長公共子序列的長度。子問題即為L[i][j]。

分三種情況：
1、當(dāng)$j>n$ 返回0。
2、當(dāng)$S[i]>=S[j]$時，此時$jn$中均大于$S[i]$的最長遞增子序列一定不包含$S[j]$，因此返回 $L(i,j+1)$。
3、$S[i]<S[j]$，此時要選擇更長的遞增子序列，返回$max(L(i,j+1),L(j,j+1)+1)$。

轉(zhuǎn)移方程：

時間復(fù)雜度： 填表過程中，有兩個參數(shù)，因此有兩輪循環(huán)，因此時間復(fù)雜度：
$$T(n)=O(n^2)$$

空間復(fù)雜度： 備忘錄為一個二維的數(shù)組，因此空間復(fù)雜度：
$$S(n)=O(n^2)$$

代碼：

int lis_dp2(const vector<int>& s, int n) {
    vector<vector<int>> Lis(s.size()+1,vector<int>(s.size()+1,0));
    for(int i=n;i>=0;i--){
        for(int j=n;j>=i;j--){
            if(s[i]>=s[j]) Lis[i][j]=Lis[i][j+1];
            else Lis[i][j]=max(1+Lis[j][j+1], Lis[i][j+1]);
        }
    }
    return Lis[0][1];
}

算法二：L[i][j]改進，求最長遞增子序列

思路： 基于 算法二 得到最終的L。觀察動態(tài)規(guī)劃的轉(zhuǎn)移方程可以知道，只有在$L[i][j]=L[j][j+1]+1$時，才會有遞增子序列的序列長度的增加。因此利用該條件，定義i=0、j=1、len=L[0][1]，從L[0][1]開始，如果$Lis[j][j+1]==len?1$，那么該元素即為最長遞增子序列中的元素，len自減，i更新為j，j更新為j+1，直至len變?yōu)?。

時間復(fù)雜度： 原時間復(fù)雜度為$O(n^2)$，修改之后只在最外層增加了一個循環(huán)，所以總的時間復(fù)雜度：$$T(n)=O(n^2)$$

空間復(fù)雜度： 原空間復(fù)雜度為$O(n)$，只增加了一維的數(shù)組，因此總的空間復(fù)雜度度為：$$S(n)=O(n)$$

代碼：

vector<int> find_lis_dp2(const vector<int>& s, int n) {
    vector<vector<int>> Lis(s.size()+1,vector<int>(s.size()+1,0));
    for(int i=n;i>=0;i--){
        for(int j=n;j>=i;j--){
            if(s[i]>=s[j]) Lis[i][j]=Lis[i][j+1];
            else Lis[i][j]=max(1+Lis[j][j+1], Lis[i][j+1]);
        }
    }
    int len=Lis[0][1],i=0,j=1;
    vector<int> L;
    while(len){
        if(Lis[j][j+1]==len-1){
            L.push_back(s[j]);
            i=j;j=j+1;
            len--;
        }else{
            j=j+1;
        }
    }
    return L;
}

算法三：L[k]，存儲長度為k的最小的數(shù)字

定義k，$L[k]$代表著長度為k的遞增子序列中，最小元素的值。備忘錄即為L。
$L[1]<L[2]<L[3]...$，當(dāng)遍歷到k時，此時我們只需要對比S[k]與L中各個值的大小。S[k]一定能構(gòu)成一個遞增子序列，我們要給S[k]在L中尋找一個位置，讓L一直保持遞增狀態(tài)，直到S遍歷完成。

時間復(fù)雜度： 時間花銷主要在兩個步驟：遍歷S($O(n)$)，同時給S[k]在L中尋找合適的位置($O(logn)$)。二者是嵌套的，因此整體的時間復(fù)雜度：$$T(n)=O(nlogn)$$

空間復(fù)雜度： 創(chuàng)建了一個備忘錄用于存儲元素值，因此空間復(fù)雜度為：$$S(n)=O(n)$$

代碼：

int lis_dp3(const vector<int>& s, int n) {
    vector<int> Lis;
    for(int i=1;i<=n;i++){
        auto cnt = lower_bound(Lis.begin(),Lis.end(),s[i]);
        if(cnt==Lis.end()) Lis.push_back(s[i]);
        else Lis[cnt-Lis.begin()]=s[i];
    }
    return Lis.size();
}

算法三：L[k]，改進

算法三中，L在更新的過程中會出現(xiàn)最長公共子序列的完整序列，因此只需要判斷什么時候出現(xiàn)即可。當(dāng)S[k]大于所有的L中的元素時，此時L中的所有元素構(gòu)成的是從1~k的一個最長公共子序列。隨著，不斷地在L末尾添加元素，最后那一次在L末尾添加元素時，該序列即為我們要求的最長公共子序列。

時間復(fù)雜度： 原時間復(fù)雜度為$O(nlogn)$，為添加嵌套循環(huán)，所以總的時間復(fù)雜度：$$T(n)=O(nlogn)$$

空間復(fù)雜度： 原空間復(fù)雜度為$O(n)$，只增加了一維的數(shù)組，因此總的空間復(fù)雜度度為：$$S(n)=O(n)$$

代碼：

vector<int> find_lis_dp3(const vector<int>& s, int n) {
    vector<int> Lis, L;
    int index=0;
    for(int i=1;i<=n;i++){
        auto cnt = lower_bound(Lis.begin(),Lis.end(),s[i]);
        if(cnt==Lis.end()){
            Lis.push_back(s[i]);
            index=i;
        }
        else Lis[cnt-Lis.begin()]=s[i];
    }
    cout<<index<<endl;
    for(int i=1;i<=index;i++){
        auto cnt = lower_bound(L.begin(),L.end(),s[i]);
        if(cnt==L.end()) L.push_back(s[i]);
        else L[cnt-L.begin()]=s[i];
    }
    return L;
}

鋪地毯

題目：
給定?個3n的棋盤， 設(shè)計?個動態(tài)規(guī)劃算法計算有多少種使?12的?牌進?完美覆蓋的?案。完美覆蓋是指沒有未覆蓋的?格，也沒有堆疊或者懸掛在棋盤外的?牌.

思路
首先如果棋盤的列數(shù)是奇數(shù)，那總的棋盤格子也是奇數(shù)，無法滿足要求。因此只有列數(shù)是偶數(shù)時，才能求解方案數(shù)。

當(dāng)$n=2$時，$dp[n]=3$。

當(dāng)$n=4$時，我們也能很快的計算得到$dp[n]=11$，下面是一些例子：
在例子中，我們可以觀察到一定的現(xiàn)象，示例圖主要有兩個類別：第一種：存在2*3的棋盤可以與剩下棋盤的骨牌區(qū)域分割開來、第二種：整個棋盤是一起的，不能分割成k*3的小塊。

當(dāng)$n=6$，繪制出部分實例。可以看到示例圖主要分三個類別：1、分為3個23的子棋盤。2、分為一個23的子棋盤和一個43的整體的子棋盤。3、只有一個大的63的子棋盤。

將上述三種列別分別計算求和：$3?3?3+2?3?2+2?1=41$

當(dāng)$n=8$時：根據(jù)示例觀察，我們可以得到四個類別。1、最后的一個整體為23。2、最后的一個整體為43。3、最后的一個整體為63。4、最后的一個整體為83。

易證得，該四個類別之間沒有交集，且其數(shù)量之和為解：
無交集：最后一個整體為23，與最后一個整體為43，此時都確定了一個小塊區(qū)域與對方不一致，不管剩下的一塊怎么放置，整體都不會完全一樣。剩下的類別也是類似。
數(shù)量之和為解：8*3的放置方式可以看做是6*3的基礎(chǔ)上多了一個2*3+4*3的基礎(chǔ)上多了一個4*3+2*3的基礎(chǔ)上多了一個6*3+8*3為一個整體的。這些類別其實就與上述示例圖的類別一致。

最終觀察n=6、n=4都能不斷地從后往前，確定整體小塊棋盤的大小(從2開始，不斷的增加，直至n)。

轉(zhuǎn)移方程：

時間復(fù)雜度： 需要兩層遍歷：$$T(n)=O(n^2)$$。

空間復(fù)雜度： 創(chuàng)建了一個一維的數(shù)組，因此空間復(fù)雜度為$$S(n)=O(n)$$。

代碼：

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;


int countWays(int n) {
    if(n%2!=0) return 0;
    vector<int> v(n+1,0);
    v[0]=1;
    for(int i=2;i<=n;i+=2){
        int cnt = 3*v[i-2];
        for(int j=i-4;j>=0;j-=2){
            cnt+=v[j]*2;
        }
        v[i]=cnt;
    }
    return v[n];
}

int main() {
    int n = 6;
    cout << countWays(n) << endl;

    return 0;
}

棋盤放石子

題目：
一個4行n列的棋盤，每個正方形上都寫著一個整數(shù)。有一組2n個鵝卵石，可以將所有或期中一部分鵝卵石放置在棋盤的正方形中（每個鵝卵石可以正好放在一個正方形上），以便最大化鵝卵石覆蓋的正方形中的整數(shù)之和。
放置鵝卵石的方式有一個約束：為了使鵝卵石的放置合法，它們中的兩個不能在水平或垂直相鄰的正方形上（對角線相鄰是可以的）。

思路：
對于4*n的棋盤，如果整體考慮，會很復(fù)雜。我們將每一列單獨考慮，每一列只有四個值，要求每行每列的數(shù)都不相鄰。最終每一列的情況如下：

對上述八種情況進行表示，可以將這四個位置看做二進制的一維，組成一個四位二進制數(shù)，從上往下分別代表第一位、第二位以此類推。若放置石子(即為方塊填藍色)，則對應(yīng)二進制位為1。因此最終八種狀態(tài)可以用如下數(shù)字表示：

0、1、2、4、5、7、8、9

對于不同列，如果這兩列不相鄰，則他們之間的選取并不會互相影響，因此只需要考慮相鄰的情況：

可以看到，滿足要求相鄰兩列同一行是不會同時填藍色的(基于列滿足的情況)。將其轉(zhuǎn)換成二進制運算，如果同一行均放置石子(圖中均為藍色)，那么按位于的結(jié)果一定不為0，而如果滿足題意，則按位與的情況是一定為0的，如第1和3張圖。

轉(zhuǎn)移方程：

時間復(fù)雜度： 需要有三層循環(huán)，但最里面兩層循環(huán)均是有限次的，8*8=64次，因此時間復(fù)雜度為：$$\begin{gathered} T(n)=O(64n) \\ T(n)=O(n) \end{gathered}$$

空間復(fù)雜度： 創(chuàng)建了一個二維的數(shù)組，但第二維僅有8個數(shù)，因此空間復(fù)雜度為$$\begin{gathered} S(n)=O(8n) \\ S(n)=O(n) \end{gathered}$$

代碼：

#include<iostream>
#include<vector>
using namespace std;

int countNumber(vector<vector<int>>& checkBoard, int col,int n){
    int cnt=0,i=0;
    while(n){
        if(n&1) cnt+=checkBoard[i][col];
        n>>=1;
        i++;
    }
    return cnt;
}

int placePebbles(vector<vector<int>>& checkBoard){
    int n=checkBoard[0].size();
    vector<vector<int>> dp(n,vector<int>(7,0));
    vector<int> v={1,2,4,5,8,9,10};
    for(int i=0;i<n;i++){
        for(int j=0;j<7;j++){
            dp[i][j]=countNumber(checkBoard, i,v[j]);
        }
    }
    cout<<endl;
    for(int i=1;i<n;i++){
        for(int j=0;j<7;j++){
            int cnt=0;
            for(int k=0;k<7;k++){
                if((v[j]&v[k])!=0) continue;
                cnt=max(dp[i][j]+dp[i-1][k], cnt);
            }
            dp[i][j]=max(cnt, dp[i][j]);
        }
        cout<<endl;
    }
    int ans=0;
    for(int i=0;i<7;i++){
        ans=max(ans, dp[n-1][i]);
    }
    return ans;
}

int main(){
    vector<vector<int>> checkBoard={
        {1,2,3,-4},
        {1,2,3,4},
        {1,2,3,4},
        {1,2,3,-4}
    };
    cout<<placePebbles(checkBoard)<<endl;
    return 0;
}

到了這里，關(guān)于【算法設(shè)計與分析】動態(tài)規(guī)劃-練習(xí)題的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！