【动态规划】子序列问题汇总

更新于 分类于 ， 阅读次数： 本文字数： 1.4k 阅读时长 ≈ 1 分钟

子序列问题是动态规划很常见的问题，这里做一个汇总，包括最长上升子序列、最长公共子序列、最大连续子序列的问题

LIS

最长上升子序列

（原理鸽了，有时间会来补）

1
2
3
4
5
6
7
8
9
10
11
12
// 最长上升
// a[i]是原序列，答案是len
d[0] = a[0];
int len = 1;
for (int i = 0; i < n; i++)
{
    if (d[len - 1] < a[i])
        d[len++] = a[i];    // d数组内的数值始终上升
    else
        *lower_bound(d, d + len, a[i]) = a[i];    // 找到最前面可以替换的地方
}
// 最长不上升： *upper_bound(dp,dp+len,m[i],greater<int>()) = a[i];

LCS

最长公共子序列

1
2
3
4
5
6
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        if (a[i] == b[j]) //如果第i和第j位相同，更新值
            dp[i][j] = max(dp[i - 1][j - 1] + 1, dp[i][j]);
        else //如果不相同，继承上一个状态的长度
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

最大连续子序列

连续的子序列，各位之和最大，其实这并不是个动态规划问题，归纳在这了

朴素算法

用数组sum[i]维护前缀和，两层循环就能遍历每一个子序列 {ai,ai+1,⋯ ,aj}\{a_i,a_{i+1},\cdots,a_j\} 的和sum[j]-sum[i-1]，时间复杂度 O(n2)O(n^2)

贪心

如果求和反而变小了就重新开始计算子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int maxn = 0, s = 0, t = 0;
int sum = 0, pos = 1;
for (int i = 1; i <= k; i++)
{
    sum += a[i];
    if (sum < 0)
    {
        pos = i + 1;
        sum = 0;
    }
    else if (sum > maxn)
    {
        s = pos;
        t = i;
        maxn = sum;
    }
}

动态规划

上述贪心思想如果考虑动态规划，则设dp[i]表示以a[i]结尾的连续子序列的最大和，很容易得到状态转移方程dp[i]=max(dp[i-1]+a[i],a[i])

分治

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int maxsum(int *A, int x, int y) // 返回数组在左闭右开区间[x,y)中的最大连续和
{
    if (y - x == 1)
        return A[x];                                  // 只有一个元素，直接返回
    int m = x + (y - x) / 2;                          // 划分成[x,m)和[m,y)
    int maxn = max(maxsum(A, x, m), maxsum(A, m, y)); // 递归求解
    int v = 0, L = A[m - 1], R = A[m];
    for (int i = m - 1; i >= x; i--) 
        L = max(L, v += A[i]); // 找从分界点开始往左的最大连续和L
    v = 0;
    for (int i = m; i < y; i++)
        R = max(R, v += A[i]); // 找从分界点开始往右的最大连续和R
    return max(maxn, L + R); // max(左区间，右区间，横跨区间)
}