算法动态规划

优化状态表示，降低状态转移的复杂性；LCIS问题

字数统计: 2.1k字   |   阅读时长: 9分
,

摘要: 优化状态表示

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

最长上升子序列(LIS)和最长公共子序列(LCS)是单串和双串场景下的动态规划的状态设计思路。

将这两个合起来，形成最长公共上升子序列(LCIS)，这个问题相对会难一些。本文我们看一下这个问题的状态表示和阶段划分的思路。以及对状态转移方程的处理。

通过本题，我们重点看一下动态规划中的一类优化思路，通过改变状态表示，使得状态转移过程得到简化。这可以理解为一种通过优化状态表示的方法对 DP 进行优化。

另外本题还涉及到动态规划中的另一类问题，就是随着状态的推导，如果决策候选集合只增多而不减少的话，是有可能通过维护增量的决策候选而不是阶段每推进一次就把决策候选集枚举一遍，来减少重复计算。

最长公共上升子序列

对于两个数列 A 和 B，如果它们都包含一段位置不一定连续的数，且数值是严格递增的，那么称这一段数是两个数列的公共上升子序列，而所有的公共上升子序列中最长的就是最长公共上升子序列了。

求最长公共上升子序列的长度。

1
2
3
4
5
6
7
8
9
10
11
输入格式
第一行包含一个整数 N，表示数列 A，B 的长度。
第二行包含 N 个整数，表示数列 A。
第三行包含 N 个整数，表示数列 B。

输出格式
输出一个整数，表示最长公共上升子序列的长度。

数据范围
1<=N<=3000,
序列中的数字均不超过 2^31−1。

输入样例：
4
2 2 1 3
2 1 2 3
输出样例：
2

线性动态规划

参考 LIS 的状态定义和阶段划分方式，定义状态 $dp[i][j]$ 表示考虑 $A[0..i]$, $B[0..j]$ 且以 $A[i]$, $B[j]$ 结尾的 LCIS 长度。阶段划分为 $A$ 已经算完的前缀以及 $B$ 已经算完的前缀。

考虑 $dp[i][j]$ 的最优子结构。如果 $A[i] \neq B[j]$，则很直接 $dp[i][j] = 0$。

在 $A[i] = B[j]$ 的情况下：

  • $A$ 要满足上升子序列的话需要找 $k < i, A[k] < A[i]$ 的 $k$
  • $B$ 要满足上升子序列的话需要找 $l < j, B[l] < B[j]$ 的 $l$

这两个子序列是公共子序列，还需要 $A[k] = B[l]$，由此写出状态转移方程。

当 $A[i] = B[j]$ 时：

答案为 $max(dp[i][j])$。

代码 (C++)

$O(N^{4})$

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
#include <vector>
#include <iostream>

using namespace std;

int lcis(const vector<int> &A, const vector<int> &B)
{
    int N = A.size();
    vector<vector<int> > dp(N, vector<int>(N, 0));
    int ans = 0;
    for(int i = 0; i < N; ++i)
        for(int j = 0; j < N; ++j)
            if(A[i] == B[j])
            {
                for(int k = 1; k < i; ++k)
                    for(int l = 1; l < j; ++l)
                        if(A[k] < A[i] && B[l] < B[j])
                            dp[i][j] = max(dp[i][j], dp[k][l]);
                dp[i][j] += 1;
                ans = max(ans, dp[i][j]);
            }
    return ans;
}

int main()
{
    int N;
    cin >> N;
    vector<int> A(N);
    vector<int> B(N);
    for(int i = 0; i < N; ++i)
        cin >> A[i];
    for(int i = 0; i < N; ++i)
        cin >> B[i];
    int ans = lcis(A, B);
    cout << ans << endl;
}

优化状态表示

将前面的状态定义中，$i$ 这个维度表示考虑 $A$ 的前 $i$ 个元素，且以 $A[i]$ 结尾；$j$ 这个维度表示考虑 $B$ 的前 $j$ 个元素，且以 $B[j]$ 结尾。

参考 LCS 的状态定义和阶段划分方式，可以尝试在 $i$ 维度的定义中去掉“以 $A[i]$ 结尾”，这样状态定义为 $dp[i][j]$ 表示考虑 $A[0..i]$, $B[0..j]$ 且以 $B[j]$ 结尾的 LCIS 长度。阶段划分还是为 $A$ 已经算完的前缀以及 $B$ 已经算完的前缀。

$dp[i][j]$ 表示考虑 $A[0..i]$, $B[0..j]$ 且以 $A[i]$, $B[j]$ 结尾的 LCIS 长度。阶段划分为 $A$ 已经算完的前缀以及 $B$ 已经算完的前缀。

这样的话答案就变成了 $max(dp[N-1][j])$。

修改了状态定义之后，在 $A[i] \neq B[j]$ 时，之前只能定义 $dp[i][j] = 0$，而现在变成了 $dp[i][j] = dp[i - 1][j]$，这里与 LCS 类似。

当 $A[i] = B[j]$ 时：

代码 (C++)

$O(N^{3})$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int lcis(const vector<int> &A, const vector<int> &B)
{
    int N = A.size();
    vector<vector<int> > dp(N, vector<int>(N, 0));
    for(int i = 0; i < N; ++i)
        for(int j = 0; j < N; ++j)
        {
            if(A[i] == B[j])
            {
                int mv = 0;
                for(int l = 1; l < j; ++l)
                    if(B[l] < B[j] and i > 0)
                        mv = max(mv, dp[i - 1][l]);
                dp[i][j] = mv + 1;
            }
            else if(i > 0)
                dp[i][j] = dp[i - 1][j]; 
        }

    int ans = 0;
    for(int i = 0; i < N; ++i)
        ans = max(ans, dp[N - 1][i]);
    return ans;
}

决策单调性：决策集合递增而目标函数不变

回顾原来的转移方程中 $\max$ 的部分：

在转移的过程中，把满足 $0 \leq l < j, B[l] < B[j]$ 的 $l$ 构成的集合称为状态 $dp[i][j]$ 转移时的决策集合，记为 $S(i, j)$。

注意这里的特点，$\max$ 的指标 $l$ 的范围与 $i$ 无关，$\max$ 的目标函数与 $j$ 无关。

在前面代码中的第二层循环 $j = 0\cdots N-1$ 中，第一层循环 $i$ 是定值，这使得条件 $B[l] < B[j]$(也就是 $B[l] < A[i]$) 是固定的。

因此当 $j \rightarrow j + 1$ 时，$k$ 的取值范围从 $[0, j)$ 变为 $[0, j+1)$，即 $j$ 有可能进入新的决策集合，即 $S(i, j)$ 与 $S(i, j + 1)$ 的区别仅在于 $j$ 是否加入。这只需要判断 $B[j] < A[i]$ 即可。即：

这是一个在状态推导过程中（$i$ 固定，$j$ 推导），决策集合始终只增多不减少的情况。同时目标函数与推导的变量$j$无关，即目标函数不变，因此没当 $j \rightarrow j + 1$ 时，判断是否把可能新加入候选集的决策（在这个问题中是 $j$）加入决策候选集即可。这里决策候选集是单调增加的，目标函数不变，最优决策自然也单调增加，这可以理解为是决策单调性的一种简单情况。

具体实现方法是可以用一个变量维护新加入决策候选集的决策对后续阶段的状态的贡献，在这个问题中的维护方式如下：

1
2
// 若 B[j] < A[i]，j 加入决策候选集，以下是 j 决策对后续阶段的状态的贡献
mv = max(dp[i - 1][j])

综合起来，新的转移方程如下：

1
2
3
dp[i][j] = dp[i - 1][j]                  (A[i] != B[j])
mv = max(mv, dp[i - 1][j])               (A[i] < B[j])
dp[i][j] = 1 + mv                        (A[i] == B[j])

代码 (C++)

$O(N^{2})$

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
int lcis(const vector<int> &A, const vector<int> &B)
{
    // 优化1的基础上对代码做等价变形
    int N = A.size();
    vector<vector<int> > dp(N, vector<int>(N, 0));
    for(int i = 0; i < N; ++i)
    {
        int mv = 0;
        for(int j = 0; j < N; ++j)
        {
            if(A[i] == B[j])
                dp[i][j] = mv + 1;
            else if(i > 0)
            {
                dp[i][j] = dp[i - 1][j];
                if(B[j] < A[i])
                    mv = max(mv, dp[i - 1][j]);
            }
        }
    }

    int ans = 0;
    for(int i = 1; i < N; ++i)
        ans = max(ans, dp[N - 1][i]);
    return ans;
}
Share