【算法设计与分析】动态规划-练习题

最长递增子序列

输入一个整数数组S[n]，计算其最长递增子序列的长度，及其最长递增子序列。

算法一：L[k]

定义$k(1\le k\le n)$，L[k]表示以 S[k] 结尾的递增子序列的最大长度。子问题即为 L[k]。
对于每一个k，我们都遍历前面0~k-1的所有的数，找出最大的L[i]，且$S[k]>L[i]$，此时$L[k]=L[j]+1$。不断地维护当前的最大的递增子序列的长度。

转移方程：

时间复杂度： 填表过程从1~n遍历一次 $O(n)$，在填L[k]时遍历了一次L[1…k-1] $O(n)$。因此时间复杂度：$$T(n)=O(n^2)$$
空间复杂度： 创建了备忘录L[n]，因此空间复杂度: $$S(n)=O(n)$$

代码：文章来源地址https://www.toymoban.com/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，同时在填表过程中不断维护出现最长递增子序列的元素的下标index。i从下标index-1开始，不断往前遍历，当$s[i]<s[index]\&\&L[i]+1==L[index]$时，S[i]即为最长递增子序列的元素。

时间复杂度： 基于算法一进行改进，原时间复杂度$O(n^2)$。但没有进行循环的再嵌套，只是在外层增加了一个while循环用于找到最长递增子序列，时间复杂度为$O(n)$。因此总的时间复杂度为：$$T(n)=O(n^2)$$

空间复杂度： 基于算法一进行改进，原空间复杂度$O(n)$。只新创建了一个一维数组，空间复杂度为$O(n)$。因此总的空间复杂度度为：$$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、当$j>n$ 返回0。
2、当$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)$。

转移方程：

时间复杂度： 填表过程中，有两个参数，因此有两轮循环，因此时间复杂度：
$$T(n)=O(n^2)$$

空间复杂度： 备忘录为一个二维的数组，因此空间复杂度：
$$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。观察动态规划的转移方程可以知道，只有在$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变为0。

时间复杂度： 原时间复杂度为$O(n^2)$，修改之后只在最外层增加了一个循环，所以总的时间复杂度：$$T(n)=O(n^2)$$

空间复杂度： 原空间复杂度为$O(n)$，只增加了一维的数组，因此总的空间复杂度度为：$$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的最小的数字

定义k，$L[k]$代表着长度为k的递增子序列中，最小元素的值。备忘录即为L。
$L[1]<L[2]<L[3]...$，当遍历到k时，此时我们只需要对比S[k]与L中各个值的大小。S[k]一定能构成一个递增子序列，我们要给S[k]在L中寻找一个位置，让L一直保持递增状态，直到S遍历完成。

时间复杂度： 时间花销主要在两个步骤：遍历S($O(n)$)，同时给S[k]在L中寻找合适的位置($O(logn)$)。二者是嵌套的，因此整体的时间复杂度：$$T(n)=O(nlogn)$$

空间复杂度： 创建了一个备忘录用于存储元素值，因此空间复杂度为：$$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在更新的过程中会出现最长公共子序列的完整序列，因此只需要判断什么时候出现即可。当S[k]大于所有的L中的元素时，此时L中的所有元素构成的是从1~k的一个最长公共子序列。随着，不断地在L末尾添加元素，最后那一次在L末尾添加元素时，该序列即为我们要求的最长公共子序列。

时间复杂度： 原时间复杂度为$O(nlogn)$，为添加嵌套循环，所以总的时间复杂度：$$T(n)=O(nlogn)$$

空间复杂度： 原空间复杂度为$O(n)$，只增加了一维的数组，因此总的空间复杂度度为：$$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的棋盘， 设计⼀个动态规划算法计算有多少种使⽤12的⻣牌进⾏完美覆盖的⽅案。完美覆盖是指没有未覆盖的⽅格，也没有堆叠或者悬挂在棋盘外的⻣牌.

思路
首先如果棋盘的列数是奇数，那总的棋盘格子也是奇数，无法满足要求。因此只有列数是偶数时，才能求解方案数。

当$n=2$时，$dp[n]=3$。

当$n=4$时，我们也能很快的计算得到$dp[n]=11$，下面是一些例子：
在例子中，我们可以观察到一定的现象，示例图主要有两个类别：第一种：存在2*3的棋盘可以与剩下棋盘的骨牌区域分割开来、第二种：整个棋盘是一起的，不能分割成k*3的小块。

当$n=6$，绘制出部分实例。可以看到示例图主要分三个类别：1、分为3个23的子棋盘。2、分为一个23的子棋盘和一个43的整体的子棋盘。3、只有一个大的63的子棋盘。

将上述三种列别分别计算求和：$3\ast 3\ast 3+2\ast 3\ast 2+2\ast 1=41$

当$n=8$时：根据示例观察，我们可以得到四个类别。1、最后的一个整体为23。2、最后的一个整体为43。3、最后的一个整体为63。4、最后的一个整体为83。

易证得，该四个类别之间没有交集，且其数量之和为解：
无交集：最后一个整体为23，与最后一个整体为43，此时都确定了一个小块区域与对方不一致，不管剩下的一块怎么放置，整体都不会完全一样。剩下的类别也是类似。
数量之和为解：8*3的放置方式可以看做是6*3的基础上多了一个2*3+4*3的基础上多了一个4*3+2*3的基础上多了一个6*3+8*3为一个整体的。这些类别其实就与上述示例图的类别一致。

最终观察n=6、n=4都能不断地从后往前，确定整体小块棋盘的大小(从2开始，不断的增加，直至n)。

转移方程：

时间复杂度： 需要两层遍历：$$T(n)=O(n^2)$$。

空间复杂度： 创建了一个一维的数组，因此空间复杂度为$$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列的棋盘，每个正方形上都写着一个整数。有一组2n个鹅卵石，可以将所有或期中一部分鹅卵石放置在棋盘的正方形中（每个鹅卵石可以正好放在一个正方形上），以便最大化鹅卵石覆盖的正方形中的整数之和。
放置鹅卵石的方式有一个约束：为了使鹅卵石的放置合法，它们中的两个不能在水平或垂直相邻的正方形上（对角线相邻是可以的）。

思路：
对于4*n的棋盘，如果整体考虑，会很复杂。我们将每一列单独考虑，每一列只有四个值，要求每行每列的数都不相邻。最终每一列的情况如下：

对上述八种情况进行表示，可以将这四个位置看做二进制的一维，组成一个四位二进制数，从上往下分别代表第一位、第二位以此类推。若放置石子(即为方块填蓝色)，则对应二进制位为1。因此最终八种状态可以用如下数字表示：

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

对于不同列，如果这两列不相邻，则他们之间的选取并不会互相影响，因此只需要考虑相邻的情况：

可以看到，满足要求相邻两列同一行是不会同时填蓝色的(基于列满足的情况)。将其转换成二进制运算，如果同一行均放置石子(图中均为蓝色)，那么按位于的结果一定不为0，而如果满足题意，则按位与的情况是一定为0的，如第1和3张图。

转移方程：

时间复杂度： 需要有三层循环，但最里面两层循环均是有限次的，8*8=64次，因此时间复杂度为：$$\begin{gathered} T(n)=O(64n) \\ T(n)=O(n) \end{gathered}$$

空间复杂度： 创建了一个二维的数组，但第二维仅有8个数，因此空间复杂度为$$\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;
}

到了这里，关于【算法设计与分析】动态规划-练习题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！