C++知识点总结(45)：序列动态规划_C/C++

序列动态规划

一、意义
二、例题

一、意义

动态规划（dynamic programming），将一个目标大问题“大事化小，小事化了”，分成很多的子问题，得出子问题的解后得到目标大问题的解。动态规划相当于地狱难度的递推。

二、例题

1. 最长上升子序列

题目描述

输入描述

输出描述

样例1

提示

先来推出状态转移方程（以样例1为例）：

a[]	1	7	3	5	9	4	10
子序列	1	1,7	1,3	1,3,5	1,3,5,9	1,3,4	1,3,5,9,10
dp[]	1	2	2	3	4	3	5

在上面的列举中，dp[i] 表示的是以 a[i] 为子序列末尾的长度最大值。

而我们求出 dp[i] 的方法也有些麻烦：

向前遍历 a[]：
- 如果满足 a[i]>a[k]（当前遍历到的数字 a[i] 比之前遍历到的数字 a[k] 大）
- 打擂台求 dp[i] 的最大值

综合的时间复杂度大约是 $o(n^2)$ ，感觉勉强能过。

综上所述，我们写出如下代码：

#include <iostream>
using namespace std;

int n, maxn;
int a[1005];
int dp[1005];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    
    for (int i = 1; i <= n; i++)
        for (int k = i-1; k >= 1; k--)
            if (a[k] < a[i])
            {
                dp[i] = max(dp[i], dp[k]+1);
                maxn = max(maxn, dp[i]);
            }
    
    cout << maxn+1;
    return 0;
}

2. 合唱队形（加强版）

题目描述

输入描述

输出描述
一个整数，最少需要几位同学出列

样例1

提示

这道题目就是上一道题的加强版。这道题目会有两个 dp[] 数组：

dp1[i]：以 a[i] 为子序列结尾的最长上升子序列
dp2[i]：以 a[i] 为子序列结尾的最长下降子序列

那么就有如下代码：

#include <iostream>
using namespace std;

int n, maxn;
int a[100005];
int dp1[100005];
int dp2[100005];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    for (int i = 1; i <= n; i++)
    {
        dp1[i] = 1;
        for (int j = 1; j < i; j++)
            if (a[i] > a[j])
                dp1[i] = max(dp1[i], dp1[j]+1);
    }

    for (int i = n; i >= 1; i--)
    {
        dp2[i] = 1;
        for (int j = n; j > i; j--)
            if (a[i] > a[j])
                dp2[i] = max(dp2[i], dp2[j]+1);
    }
    
    for (int i = 1; i <= n; i++)
        maxn = max(maxn, dp1[i]+dp2[i]-1);

    cout << n-maxn;
    return 0;
}

可是这样多半是超时。那么我们可以用一个数组 b[i] 来存储长度为 i 的情况下最后的一个值。这样，对于第一题的 $< 1, 3 >$ 和 $< 1, 7 >$ 就会选择 $< 1, 3 >$ 了。即：

a[]	1	7	3	5	9	4	10
子序列	1	1,7	1,3	1,3,5	1,3,5,9	1,3,4	1,3,5,9,10
dp[]	1	2	2	3	4	3	5
b[]	1	1,7	1,3	1,3,5	1,3,5,9	1,3,4,9	1,3,4,9,10

所以第一题的代码可以优化为：

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

int n, maxn;
int len;
int a[1005];
int b[1005];
int dp[1005];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    
    for (int i = 1; i <= n; i++)
    {
        if (a[i] > b[len])
        {
            len++;
            b[len] = a[i];
            dp[i] = len;
        }
        else
        {
            int pos = lower_bound(b+1, b+len+1, a[i]) - b;
            b[pos] = a[i];
            dp[i] = pos;
        }
    }
    
    for (int i = 1; i <= n; i++)
        maxn = max(maxn, dp[i]);
    
    cout << maxn;
    return 0;
}

作业1

3. 公共子序列

题目描述

输入描述

输出描述

样例1

提示

按照题目的描述，我们可以有一个 dp[][] 数组。其中 dp[i][j] 表示当 a 有 $i$ 个数、b 有 $j$ 个数的状态下最长的公共子序列长度。根据样例1，则有以下存储：

	2	3	4	5	6
1	0	0	0	0	0
2	0	0	0	0	0
3	1	1	1	1	1
4	1	2	2	2	2
5	1	2	3	3	3

所以得出式子：

a[i] == b[i]
- dp[i][j] = dp[i-1][j-1]
a[i] != b[i]
- dp[i][j] = max(dp[i-1][j], dp[i][j-1])

上代码：

#include <iostream>
using namespace std;

int n, m;
int a[1005];
int b[1005];
int dp[1005][1005];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= m; i++)
        cin >> b[i];
    
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            if (a[i] == b[j])
                dp[i][j] = dp[i-1][j-1]+1;
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    
    cout << dp[n][m];
    return 0;
}

4. 编辑距离

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

string a, b;
int dp[2005][2005];

int main()
{
    cin >> a >> b;
    
    int lena = a.length();
    int lenb = b.length();
    a = ' ' + a;
    b = ' ' + b;
    
    for (int i = 1; i <= lena; i++)
        dp[i][0] = i;
    for (int j = 1; j <= lenb; j++)
        dp[0][j] = j;
    
    for (int i = 1; i <= lena; i++)
        for (int j = 1; j <= lenb; j++)
        {
            if (a[i] == b[j])
                dp[i][j] = min({dp[i-1][j-1], dp[i-1][j]+1, dp[i][j-1]+1});
            else
                dp[i][j] = min({dp[i-1][j-1]+1, dp[i-1][j]+1, dp[i][j-1]+1});
        }
    cout << dp[lena][lenb];
    return 0;
}