算法动态规划

LIS和LCS拾遗,LCIS

字数统计: 1.2k字   |   阅读时长: 5分
  • LIS 基础
  • LCS 基础
  • LIS 划分
    • dilworth 定理
    • 变形
  • LCS 转 LIS
  • LCIS
    • 优化1: 对状态表示和阶段划分的优化
    • 优化2: 代码等价变形

$0 LIS 和 LCS 基础

$1 LIS 划分

问题

给定一个数组，可以将其划分为若干个上升子序列，求划分的上升子序列的最少的个数。

分析

Dilworth 定理及其对偶定理：

  • 最少链划分数 = 最长反链长度
  • 最少反链划分数 = 最长链长度

参考 : 【冯荣权】组合数学拾遗2-偏序集,Dilworth定理

算法

求最少上升子序列划分数，等于求最长非升子序列长度。

$2 LCS 转 LIS

对于 LCS 问题，使用动态规划可以得到 $O(NM)$ 的算法，对于 LIS 问题，使用二分可以得到 $O(N\log N)$ 的算法。

有一些 LCS 问题可以转换为 LIS 问题，进而得到更好的时间复杂度。但是只有某些特定的问题可以转换。

如果两串 A, B 中均没有重复元素，可以预处理一个辅助串 C。按顺序枚举每个 B 中的元素 b，如果 b 在 A 中有出现(只出现一次)，则将 b 在 A 中出现位置的下标按顺序插入 C 中，这样预处理后，求 A, B 的 LCS 就转化为求 C 的 LIS。

如果 A, B 有重复元素，b 在 A 中有多个下标，将这些下标打包插入 C 中，同一包内的下标倒序排列，倒序排列后，在求 LIS 时，每一个包自然只能选一个。但是这样处理后时间复杂度可能会变得不可控。

$3 最长公共上升 LCIS

线性动态规划

1
2
3
4
5
6
dp[i][j] := 考虑 A[0..i], B[0..j] 且以 A[i], B[j] 结尾的 LCIS 长度

转移
dp[i][j] = 0                    (A[i] != B[j])
         = 1 + max(dp[k][l])    (A[i] == B[j])
           其中 k < i, l < j , 且要满足 A[k] < A[i], B[l] < B[j]

代码

$O(N^{4})$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void lcis(const vector<int> &A, const vector<int> &B)
{
    int N = A.size();
    vector<vector<int> > dp(N + 1, vector<int>(N + 1, 0));
    int ans = 0;
    for(int i = 1; i < N; ++i)
        for(int j = 1; 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]);
            }
    cout << ans << endl;
    return;
}

优化1

  • 优化状态表示和阶段划分
1
2
3
4
5
6
7
8
9
求 max dp[k][l] 时候，对 max 有贡献的 k,l 一定是匹配的(A[k] == B[l])
所以 max 的条件中 A[k]<A[i] 和 B[l]<B[j] 只要满足了一个，另一个一定满足

dp[i][j] := 考虑 A[0..i], B[0..j] 且 B 以 B[j] 结尾的 LCIS 长度

转移
dp[i][j] = dp[i - 1][j]         (A[i] != B[j])
         = 1 + max(dp[i - 1][l])    (A[i] == B[j])
           其中 l < j , 且要满足 B[l] < B[j]

代码

$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
void lcis(const vector<int> &A, const vector<int> &B)
{
    int N = A.size();
    vector<int> dp(N + 1, 0);
    for(int i = 1; i < N; ++i)
        for(int j = 1; j < N; ++j)
        {
            if(A[i] == B[j])
            {
                int mv = 0;
                for(int l = 1; l < j; ++l)
                    if(B[l] < B[j])
                        mv = max(mv, dp[l]);
                dp[j] = mv + 1;
            }
        }

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

}

优化2

  • 代码等价变形

原来的转移方程

1
2
3
dp[i][j] = dp[i - 1][j]             (A[i] != B[j])
         = 1 + max(dp[i - 1][l])    (A[i] == B[j])
           其中 l < j , 且要满足 B[l] < B[j]

当 (A[i] == B[j]) 时，求 max(dp[i - 1][l]) 其中 l < j , B[l] < B[j] 无需现算，因为 l < j 时的 dp[i - 1][j] 在计算 dp[i][j] 之前都看过了。因此枚举 j 求 dp[i][j] 时用一个变量 mv 维护一下最值信息即可。

1
mv = max(dp[i - 1][j]) 其中 B[j] < A[i]

新的转移方程

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])

代码

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

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