Boil's Blog HomeArchivesTagsCategories
动态规划第二讲
Word count: 3.4k|Reading time: 16 min

最长公共子序列问题(homework)

题目大意

经典的LCS问题，题目的意思是给出两个字符串，让我们找出他们之间的最大公共子序列（子序列是不用连续的）

实现思路

这里说的是一种标准动态规划思路（其实和记忆化搜索等价）。我们这里首先规定dp[ i ] [ j ]为第一个串1-i个字符和第二个串1-j个字符之间形成的最大子序列长度。s1,s2为输入的两个字符串。那么我们就可以得出转移方程，分为两种情况，第一种是s1[i]==s2[j]，那么这个时候的dp[ i ] [ j ]就相当于是dp[i-1] [j-1]再加上1。如果不相等，那么dp[i] [j]就相当于dp[i-1] [j]和dp[i] [j-1]之间取大的那个。这个不难证明其最优子结构的特性。还有一个问题是同时要把这个最长的序列输出。当然我们可以采用辅助数组记录的方法，但其实没有必要，因为我们可以通过dp数组从后往前的判断来找到每一步走的方式从而还原

实现细节

要记得进行初始化，也就是把dp[0] [x]和dp[x] [0]全部清零。同时要注意当相等的时候不是dp[i-1] [j]和dp[i] [j-1]之间取大的那个+1，而是直接取dp[i-1] [j-1]再加上1，否则会导致的问题是同一个数的重复使用。

一定要注意回溯时候的细节，注意判定条件，否则会出现只用上面元素而不用下面元素的情况

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
//
//  5th homework of Algorithm Designing and Analyzing in spring semester, 2020
//
//  Introduction:
//      Basic LCS problem using dynamic programming
//
//  Author:
//      Yihang Bao
//      2018011890
//  Created by Yihang Bao on 2020/3/31.
//
//
#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));

char s1[1010],s2[1010];
int dp[1010][1010];

int LCS(int len_s1,int len_s2)
{
    for (int i=0;i<=len_s1;i++)
        dp[i][0]=0;
    for (int i=0;i<=len_s2;i++)
        dp[0][i]=0;
    for (int i=1;i<=len_s1;i++)
        for (int j=1;j<=len_s2;j++)
        {
            if (s1[i]==s2[j])
            {
                dp[i][j] = dp[i-1][j-1]+1;
                continue;
            }
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    return dp[len_s1][len_s2];
}
void gener_LCS(int tail1, int tail2)
{
    if (tail1==0 || tail2==0)
        return;
    if (s1[tail1]==s2[tail2])
    {
        gener_LCS(tail1-1, tail2-1);
        cout << s1[tail1];
    }
    else if (dp[tail1-1][tail2]>=dp[tail1][tail2-1])
        gener_LCS(tail1-1, tail2);
    else
        gener_LCS(tail1, tail2-1);
    return;
}
int main()
{
    cin >> s1+1;
    cin >> s2+1;
    int n1 = strlen(s1+1);
    int n2 = strlen(s2+1);
    cout << LCS(n1, n2) << endl;
    gener_LCS(n1, n2);
    cout << endl;
}

最长连续公共子序列问题(homework)

题目大意

其实这类题一般称做最长连续公共字串。

实现思路

由于我这里是基于上一个问题改的代码，所以只谈谈和前一个问题的不同点。在这个问题当中，dp[i] [j]的意义变为了以s1[i]和s2[j]结尾的最长连续子序列的长度，和上题不同的是这里必须包括本身。那么相等的时候转移方程不变，而一旦相等，则直接赋值为0。同时我们在过程中要同步记录最大值以及最大值对应的结尾下标，以便还原。还原的时候只要在最终的结尾下表往前连续扫，知道不相等就到了头，把这段连续的区间输出即可

实现细节

和上面的实现细节相同，不要忘了一个都不相等的特判，否则会出错。

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
//
//  5th homework of Algorithm Designing and Analyzing in spring semester, 2020
//
//  Introduction:
//      modified from the LCS problem, here i change the meaning of dp[i][j].
//
//  Author:
//      Yihang Bao
//      2018011890
//  Created by Yihang Bao on 2020/3/31.
//
//
#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));

char s1[1010],s2[1010];
int dp[1010][1010];
int ansx,ansy;
int ret;

void LCS(int len_s1,int len_s2)
{
    for (int i=0;i<=len_s1;i++)
        dp[i][0]=0;
    for (int i=0;i<=len_s2;i++)
        dp[0][i]=0;
    for (int i=1;i<=len_s1;i++)
        for (int j=1;j<=len_s2;j++)
        {
            if (s1[i]==s2[j])
            {
                dp[i][j] = dp[i-1][j-1]+1;
                if (dp[i][j]>ret)
                {
                    ret = dp[i][j];
                    ansx = i; ansy = j;
                }
                continue;
            }
            dp[i][j] = 0;
        }
}
void gener_LCS()
{
    if (ret==0)
    {
        cout << "Failed to find" <<endl;
        return;
    }
    int headx,heady;
    for (int i=ansx,j=ansy;;i--,j--)
    {
        if (i==0 || j==0 || s1[i]!=s2[j])
        {
            headx = i+1;
            heady = j+1;
            break;
        }
    }
    for (int i=headx,j=heady;i<=ansx;i++,j++)
        cout << s1[i];
    cout << endl;
        
}
int main()
{
    cin >> s1+1;
    cin >> s2+1;
    int n1 = strlen(s1+1);
    int n2 = strlen(s2+1);
    ret =0;
    LCS(n1, n2);
    cout << ret << endl;
    gener_LCS();
}

求所有最长子序列问题(homework)

题目大意

在经典的LCD基础上要求回溯出所有可能的最长子序列

实现思路

这个用Cpp写着实有点麻烦，python写会很方便。于是我这里用了类python的编程思路，一些python特性通过通过c++ stl库里面的一些函数来解决。我们这里的思路就是每次回溯都带个当前已加入的字符串，每次找到一个就加到头里面，直到碰到临界条件就放入集合里面（之所以用集合是因为自动去重）

实现细节

因为这个题还d出了刚才普通版LCD的bug，看来临界条件不能瞎想啊。。。

这里由于刚开始输入的字符串是默认从0开始编码的，我这里特意在输入之后在前面插入了一个占位符来使字符串变为从1开始编码

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
//
//  5th homework of Algorithm Designing and Analyzing in spring semester, 2020
//
//  Introduction:
//      
//
//  Author:
//      Yihang Bao
//      2018011890
//  Created by Yihang Bao on 2020/3/31.
//
//

#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));
string s1,s2;
int dp[1010][1010];
set<string> ans;

int LCS(int len_s1,int len_s2)
{
    for (int i=0;i<=len_s1;i++)
        dp[i][0]=0;
    for (int i=0;i<=len_s2;i++)
        dp[0][i]=0;
    for (int i=1;i<=len_s1;i++)
        for (int j=1;j<=len_s2;j++)
        {
            if (s1[i]==s2[j])
            {
                dp[i][j] = dp[i-1][j-1]+1;
                continue;
            }
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    return dp[len_s1][len_s2];
}
void gener_LCS(int tail1, int tail2, string xx)
{
    if (dp[tail1][tail2]==0)
    {
        ans.insert(xx);
        return;
    }
    if (s1[tail1]==s2[tail2])
    {
        string temp;
        temp = s1[tail1];
        xx.insert(0, temp);
        gener_LCS(tail1-1, tail2-1,xx);
    }
    else if (dp[tail1-1][tail2]>dp[tail1][tail2-1])
        gener_LCS(tail1-1, tail2,xx);
    else if (dp[tail1-1][tail2]<dp[tail1][tail2-1])
        gener_LCS(tail1, tail2-1,xx);
    else
    {
        gener_LCS(tail1-1, tail2,xx);
        gener_LCS(tail1, tail2-1,xx);
    }
    return;
}

void out_all_seq()
{
    set<string>::iterator it;
    for (it =ans.begin();it!=ans.end();it++)
        cout << *it << endl;
}
int main()
{
    cin >> s1;
    cin >> s2;
    int n1 = s1.length();
    int n2 = s2.length();
    s1.insert(0, "?");
    s2.insert(0, "?");
    cout << LCS(n1, n2) << endl;
    gener_LCS(n1, n2,"");
    out_all_seq();
    cout << endl;
}

最大子矩阵问题(homework)

题目大意

给定m行n列的矩阵，求其最大子矩阵和

实现思路

我们这里的处理方式是首先通过m方的枚举来确定起始行和起始列。在确定好后，我们对这个区间维护一个纵向的前缀和，那么每次就是对这个长度为n的前缀和数组进行一个一维的最大区间和的求解，最后在整个过程中记录最大值即可。关于一维最大区间和的策略是，在往下跑的过程中，维护一个数组，表示以这个下标的值为子段最后一个的最大子段值，如果i-1小于0就把前面全舍弃，否则就加上前项

实现细节

同上

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
//
//  5th homework of Algorithm Designing and Analyzing in spring semester, 2020
//
//  Introduction:
//
//
//  Author:
//      Yihang Bao
//      2018011890
//  Created by Yihang Bao on 2020/3/31.
//
//

#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));
int mat[105][105];
int sub[105];
int s[105];
int m,n;

int submax()
{
    int ret = s[1];
    sub[1] = s[1];
    for (int i=2;i<=n;i++)
    {
        if (sub[i-1]<0)
            sub[i] = s[i];
        else sub[i] = s[i]+sub[i-1];
        ret = max(ret,sub[i]);
    }
    return ret;
}

int sum_matrix()
{
    int ans=-INF;
    for (int i=1;i<=m;i++)
    {
        fulset(s, 0);
        for (int j=i;j<=m;j++)
        {
            for(int k=1;k<=n;k++)
                s[k]+=mat[j][k];
            ans = max(ans,submax());
        }
    }
    return ans;
}

int main()
{
    cin >> m >> n;
    for (int i=1;i<=m;i++)
        for (int j=1;j<=n;j++)
            cin >> mat[i][j];
    cout << sum_matrix() << endl;
}

最大m子段和问题(homework)

题目大意

这是对最大子段和问题的一个推广，要求分成m段

实现思路

关键就是转移方程，我们在这里发现：对于一个长度为j的序列找出i个最大子段，求其最大值，那么他的最大值就相当于在子段数为i-1, 长度小于j的这么多最大值里面找到最大值，再拿他与子段数i，长度为j-1的进行一个比较，取大的那个加上本身的大小就是这个时候的最大值。这个其实用文字描述比较拗口，下面贴张图就比较好理解

如图，要求dp[ 3 ] [ 6 ]，只需比较他左边的那个，和上面那一行圈起来的之中最大的数，再加上a[ j ] 即为dp[ 3 ] [ 6 ] 的值。

实现细节

要对i，j相等的预处理，因为左上方没有值

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
//
//  5th homework of Algorithm Designing and Analyzing in spring semester, 2020
//
//  Introduction:
//
//
//  Author:
//      Yihang Bao
//      2018011890
//  Created by Yihang Bao on 2020/3/31.
//
//

#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));
int a[501];
int dp[501][501]; //dp[i][j] : formal j items divided into i subsets

int max_sum(int n,int m)
{
    for (int i=0;i<=n;i++)
        dp[0][i] = 0;
    for (int i=0;i<=m;i++)
        dp[i][0] = 0;
    for (int i=1;i<=m;i++)
    {
        dp[i][i] = dp[i-1][i-1] + a[i];
        int submax = dp[i-1][i-1];
        for (int j=i+1;j<=n;j++)
        {
            submax = max(submax,dp[i-1][j-1]);
            dp[i][j] = max(submax,dp[i][j-1]) + a[j];
        }
    }
    int ret = -INF;
    for (int i=m;i<=n;i++)
        ret = max(ret,dp[m][i]);
    return ret;
}

int main()
{
    int n,m;
    cin >> n >> m; //m subsets
    for (int i=1;i<=n;i++)
        cin >> a[i];
    cout << max_sum(n, m) << endl;
}

01背包问题(homework)

题目大意

经典的01背包问题，意思是每个东西只有一样，取或者不取，找最大值

实现思路

实现思路非常经典，定义一个dp[i] [j]数组用于记录前i个物品放到容量大小为j的空间时所能得到的最大值。 然后后面还有一个traceback操作，是通过从最后一个开始往前回溯取还是不取

实现细节

这道题的实现细节比较多。首先我们是除了基本的dp判断外，还要对如果空间容量比该物品小的部分单独处理，否则会导致访问越界。还有一个细节就是在实现TraceBack的时候要注意从后往前回溯并且每找到一个就要记得把这个对应的重量从容量中减去，否则会出现问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
//
//  8th homework of Algorithm Designing and Analyzing in spring semester, 2020
//
//  Introduction:
//
//
//  Author:
//      Yihang Bao
//      2018011890
//  Created by Yihang Bao on 2020/4/15.
//
//

#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x))

struct item
{
    int w;
    int v;
};

item a[101];
int dp[101][1010];
int n,cap;

void bag_01()
{
    fulset(dp, 0);
    for (int i=1;i<=n;i++)
    {
        for (int j=cap;j>=a[i].w;j--)
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-a[i].w]+a[i].v);
        for (int j=a[i].w-1;j>=0;j--)
            dp[i][j] = dp[i-1][j];
    }
    cout << "The max Value is :  ";
    cout << dp[n][cap] << endl;
}

void Trace_back()
{
    bool x[101];
    int tmp = cap;
    fulset(x, false);
    for (int i=n;i>=2;i--)
        if (dp[i][tmp]!=dp[i-1][tmp])
        {
            x[i] = true;
            tmp -= a[i].w;
        }
    if (dp[1][tmp])
        x[1] = true;
    cout << "We choose these items:"  << endl;
    for (int i=1;i<=n;i++)
        if (x[i])
            cout << i << " ";
    cout << endl;
}

int main()
{
    cout << "Please input number of items and the total capacity" << endl;
    cin >> n >> cap;
    cout << "Please input their weigts" << endl;
    for (int i=1;i<=n;i++)
        cin >> a[i].w;
    cout << "Please input their values" << endl;
    for (int i=1;i<=n;i++)
        cin >> a[i].v;
    bag_01();
    Trace_back();
}
Author: YihangBao
Link: https://roarboil.github.io/2020/04/01/cha3-2/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.