最长上升子序列模型

作者： 作者的头像   你好世界wxx ,  2021-02-27 16:31:52 ,  所有人可见 ,  阅读 541

3


2

最长上升子序列模型

概述

本博客内容参考自：AcWing

  • 下面将会按照下图的顺序开始讲解

image-20210227162052942.png 

/*
 * 0895. 最长上升子序列
 * 0896. 最长上升子序列II
 * 0897. 最长公共子序列
 * 1017. 怪盗基德的滑翔翼
 * 1014. 登山
 * 0482. 合唱队形
 * 1012. 友好城市
 * 1016. 最大上升子序和
 * 1010. 拦截导弹
 * 0187. 导弹防御系统
 * 0314. 低买
 * 0902. 最短编辑距离
 * 0899. 编辑距离
 * 0272. 最长公共上升子序列
 */

也可以到CSDN查看本博客：CSDN。

一. 基础模型

1.1 最长上升子序列(LIS)

问题描述

image-20210226122410126.png

分析

image-20210226144618591.png

代码

  • C++
// Created by WXX on 2021/2/26 14:50
#include <iostream>

using namespace std;

const int N = 1010;  // 多开几个数据，防止数组下标越界

int n;  // 输入数据个数
int a[N], f[N];  // a存储读入的数据，f是动态规划数据

// 时间复杂度：O(n^2)
int main() {

    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

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

    int res = 0;  // 最长上升子序列结尾位置不一定是数组的末尾
    for (int i = 1; i <= n; i++) res = max(res, f[i]);

    cout << res << endl;
    return 0;
}
  • Java 
import java.util.Scanner;

/**
 * Created by WXX on 2021/2/26 15:01
 * 时间复杂度：O(n^2)
 */
public class Main {

    public static final int N = 1010;  // 多开几个数据，防止数组下标越界

    static int n;  // 输入数据个数
    static int[] a = new int[N], f = new int[N];  // a存储读入的数据，f是动态规划数据

    public static void main(String[] args) {

        Scanner sn = new Scanner(System.in);
        n = sn.nextInt();
        for (int i = 1; i <= n; i++) a[i] = sn.nextInt();

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

        int res = 0;  // 最长上升子序列结尾位置不一定是数组的末尾
        for (int i = 1; i <= n; i++) res = Math.max(res, f[i]);

        System.out.println(res);
    }
}

最长上升子序列 II 的解法

  • 本题和上一题唯一的区别就是输入数组的大小增大了100倍，从最多1000个数据变成了最多100000个数据，如果还采用上述方法，则会TLE（超时），需要采用另外一种做法。

  • 我们使用一个数组q来记录额外的信息，从前向后考察输入的数据（存储在a数组中），用q[t]记录考察到当前元素是长度为t的上升子序列结尾的最小值，则根据定义可以推出 q 是一个严格单调上升的子序列，这可以用反证法进行证明。如下图：

image-20210226152257123.png

知道了q是严格单调递增的，于是我们可以考虑使用二分。

  • 对于当前考察的元素 a[i]，在q数组中找到小于a[i]的最大的数，假设为q[t]，则q[t+1]一定大于等于a[i]（否则q[t+1]就是小于a[i]的最大的数），然后将q[t+1]更新为a[i]，并在此过程中更新我们的答案。

  • 这种做法的时间复杂度是 $O(n*log(n))$ 的。

  • C++

// Created by WXX on 2021/2/26 14:50
#include <iostream>

using namespace std;

const int N = 100010;

int n;
int a[N], q[N];

// 时间复杂度：O(n^log(n))
int main() {

    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    int res = 0;
    q[0] = -2e9;  // q[0]设为负无穷，防止数组越界
    for (int i = 0; i < n; i++) {
        int l = 0, r = res;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        res = max(res, r + 1);
        q[r + 1]  = a[i];  // q[r]是小于a[i]的最大的数，则q[r+1]是大于等于a[i]的最小的数
    }

    cout << res << endl;
    return 0;
}
  • Java
import java.util.Scanner;

/**
 * Created by WXX on 2021/2/26 15:35
 * 时间复杂度：O(n^log(n))
 */
public class Main {

    public static final int N = 100010;

    static int n;
    static int[] a = new int[N], q = new int[N];

    public static void main(String[] args) {

        Scanner sn = new Scanner(System.in);
        n = sn.nextInt();
        for (int i = 0; i < n; i++) a[i] = sn.nextInt();

        int res = 0;
        q[0] = Integer.MIN_VALUE;  // q[0]设为负无穷，防止数组越界
        for (int i = 0; i < n; i++) {
            int l = 0, r = res;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (q[mid] < a[i]) l = mid;
                else r = mid - 1;
            }
            res = Math.max(res, r + 1);
            q[r + 1] = a[i];  // q[r]是小于a[i]的最大的数，则q[r+1]是大于等于a[i]的最小的数
        }

        System.out.println(res);
    }
}

1.2 最长公共子序列(LCS)

问题描述

image-20210226122503836.png

分析

image-20210226164357333.png

代码

  • C++
// Created by WXX on 2021/2/26 16:30
#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
char a[N], b[N];
int f[N][N];

int main() {

    scanf("%d%d", &n, &m);
    scanf("%s%s", a + 1, b + 1);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            if (a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
        }

    printf("%d\n", f[n][m]);
    return 0;
}
  • Java 
import java.util.Scanner;

/**
 * Created by WXX on 2021/2/26 16:47
 */
public class Main {

    public static final int N = 1010;

    static int n, m;
    static char[] a, b;
    static int[][] f = new int[N][N];

    public static void main(String[] args) {

        Scanner sn = new Scanner(System.in);
        n = sn.nextInt(); m = sn.nextInt();
        String s1 = " " + sn.next(), s2 = " " +sn.next();  // 为了让下标从1开始
        a = s1.toCharArray(); b = s2.toCharArray();

        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
                if (a[i] == b[j]) f[i][j] = Math.max(f[i][j], f[i - 1][j - 1] + 1);
            }
        System.out.println(f[n][m]);
    }
}

二. LIS扩展题

AcWing 1017. 怪盗基德的滑翔翼

问题描述

image-20210226143229347.png

分析

image-20210226185026994.png

代码

  • C++
// Created by WXX on 2021/2/26 18:52
#include <iostream>

using namespace std;

const int N = 110;

int n;
int a[N], f[N];

int main() {

    int T;
    cin >> T;

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

        // 正向求解LIS问题
        int res = 0;
        for (int i = 1; i <= n; i++) {
            f[i] = 1;
            for (int j = 1; j < i; j++)
                if (a[j] < a[i])
                    f[i] = max(f[i], f[j] + 1);
            res = max(res, f[i]);
        }
        // 反向求解LIS问题
        for (int i = n; i; i--) {
            f[i] = 1;
            for (int j = n; j > i; j--)
                if (a[j] < a[i])
                    f[i] = max(f[i], f[j] + 1);
            res = max(res, f[i]);
        }

        cout << res << endl;
    }
    return 0;
}
  • Java 
import java.util.Scanner;

/**
 * Created by WXX on 2021/2/26 18:59
 */
public class Main {

    public static final int N = 110;

    static int n;
    static int[] a = new int[N], f = new int[N];

    public static void main(String[] args) {

        Scanner sn = new Scanner(System.in);
        int T = sn.nextInt();

        while (T-- != 0) {
            n = sn.nextInt();
            for (int i = 1; i <= n; i++) a[i] = sn.nextInt();

            // 正向求解LIS问题
            int res = 0;
            for (int i = 1; i <= n; i++) {
                f[i] = 1;
                for (int j = 1; j < i; j++)
                    if (a[j] < a[i])
                        f[i] = Math.max(f[i], f[j] + 1);
                res = Math.max(res, f[i]);
            }
            // 反向求解LIS问题
            for (int i = n; i > 0; i--) {
                f[i] = 1;
                for (int j = n; j > i; j--)
                    if (a[j] < a[i])
                        f[i] = Math.max(f[i], f[j] + 1);
                res = Math.max(res, f[i]);
            }

            System.out.println(res);
        }
    }
}

AcWing 1014. 登山

问题描述

image-20210226143336297.png

分析

image-20210226192005552.png

代码

  • C++
// Created by WXX on 2021/2/26 19:21
#include <iostream>

using namespace std;

const int N = 1010;

int n;
int a[N];
int f[N], g[N];  // f: 上升子序列；g: 下降子序列

int main() {

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

    int res = 0;
    for (int i = 1; i <= n; i++) res = max(res, f[i] + g[i] - 1);

    cout << res << endl;
    return 0;
}
  • Java 
import java.util.Scanner;

/**
 * Created by WXX on 2021/2/26 19:30
 */
public class Main {

    public static final int N = 1010;

    static int n;
    static int[] a = new int[N];
    static int[] f = new int[N], g = new int[N];

    public static void main(String[] args) {

        Scanner sn = new Scanner(System.in);
        n = sn.nextInt();
        for (int i = 1; i <= n; i++) a[i] = sn.nextInt();

        for (int i = 1; i <= n; i++) {
            f[i] = 1;
            for (int j = 1; j < i; j++)
                if (a[j] < a[i])
                    f[i] = Math.max(f[i], f[j] + 1);
        }
        for (int i = n; i > 0; i--) {
            g[i] = 1;
            for (int j = n; j > i; j--)
                if (a[j] < a[i])
                    g[i] = Math.max(g[i], g[j] + 1);
        }

        int res = 0;
        for (int i = 1; i <= n; i++) res = Math.max(res, f[i] + g[i] - 1);
        System.out.println(res);
    }
}

AcWing 482. 合唱队形

问题描述

image-20210226143423383.png

分析

  • 和上一题：AcWing 1014. 登山，基本一样，唯一不同的一点是最后需要输出 n-res。

代码

  • C++
// Created by WXX on 2021/2/26 19:42
#include <iostream>

using namespace std;

const int N = 1010;

int n;
int a[N];
int f[N], g[N];  // f: 上升子序列；g: 下降子序列

int main() {

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

    int res = 0;
    for (int i = 1; i <= n; i++) res = max(res, f[i] + g[i] - 1);

    cout << n - res << endl;
    return 0;
}
  • Java 
import java.util.Scanner;

/**
 * Created by WXX on 2021/2/26 19:45
 */
public class Main {

    public static final int N = 1010;

    static int n;
    static int[] a = new int[N];
    static int[] f = new int[N], g = new int[N];

    public static void main(String[] args) {

        Scanner sn = new Scanner(System.in);
        n = sn.nextInt();
        for (int i = 1; i <= n; i++) a[i] = sn.nextInt();

        for (int i = 1; i <= n; i++) {
            f[i] = 1;
            for (int j = 1; j < i; j++)
                if (a[j] < a[i])
                    f[i] = Math.max(f[i], f[j] + 1);
        }
        for (int i = n; i > 0; i--) {
            g[i] = 1;
            for (int j = n; j > i; j--)
                if (a[j] < a[i])
                    g[i] = Math.max(g[i], g[j] + 1);
        }

        int res = 0;
        for (int i = 1; i <= n; i++) res = Math.max(res, f[i] + g[i] - 1);
        System.out.println(n - res);
    }
}

AcWing 1012. 友好城市

问题描述

image-20210226143512016.png

分析

image-20210226200611593.png

代码

  • C++
// Created by WXX on 2021/2/26 19:58
#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 5010;

int n;
PII q[N];
int f[N];

int main() {

    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d%d", &q[i].first, &q[i].second);
    sort(q, q + n);

    int res = 0;
    for (int i = 0; i < n; i++) {
        f[i] = 1;
        for (int j = 0; j < i; j++)
            if (q[j].second < q[i].second)
                f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
    }
    printf("%d\n", res);
    return 0;
}
  • Java 
import java.util.Arrays;
import java.util.Scanner;

/**
 * Created by WXX on 2021/2/26 20:07
 */
public class Main {

    static class MyPair implements Comparable<MyPair> {
        int x, y;
        public MyPair(int x, int y) {
            this.x = x;
            this.y = y;
        }
        @Override
        public int compareTo(MyPair o) { return this.x - o.x; }
    }

    public static final int N = 5010;

    static int n;
    static MyPair[] q;
    static int[] f = new int[N];

    public static void main(String[] args) {

        Scanner sn = new Scanner(System.in);
        n = sn.nextInt();
        q = new MyPair[n];
        for (int i = 0; i < n; i++) q[i] = new MyPair(sn.nextInt(), sn.nextInt());
        Arrays.sort(q);

        int res = 0;
        for (int i = 0; i < n; i++) {
            f[i] = 1;
            for (int j = 0; j < i; j++)
                if (q[j].y < q[i].y)
                    f[i] = Math.max(f[i], f[j] + 1);
            res = Math.max(res, f[i]);
        }
        System.out.println(res);
    }
}

AcWing 1016. 最大上升子序列和

问题描述

image-20210226143547538.png

分析

image-20210226202009950.png

代码

  • C++
// Created by WXX on 2021/2/26 20:15
#include <iostream>

using namespace std;

const int N = 1010;

int n;
int a[N], f[N];

int main() {

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

    int res = 0;
    for (int i = 1; i <= n; i++) {
        f[i] = a[i];
        for (int j = 1; j < i; j++)
            if (a[j] < a[i])
                f[i] = max(f[i], f[j] + a[i]);
        res = max(res, f[i]);
    }
    cout << res << endl;
    return 0;
}
  • Java 
import java.util.Scanner;

/**
 * Created by WXX on 2021/2/26 20:22
 */
public class Main {

    public static final int N = 1010;

    static int n;
    static int[] a = new int[N], f = new int[N];

    public static void main(String[] args) {

        Scanner sn = new Scanner(System.in);
        n = sn.nextInt();
        for (int i = 1; i <= n; i++) a[i] = sn.nextInt();

        int res = 0;
        for (int i = 1; i <= n; i++) {
            f[i] = a[i];
            for (int j = 1; j < i; j++)
                if (a[j] < a[i])
                    f[i] = Math.max(f[i], f[j] + a[i]);
            res = Math.max(res, f[i]);
        }
        System.out.println(res);
    }
}

AcWing 1010. 拦截导弹

问题描述

image-20210226143620539.png

分析

image-20210226221352790.png

代码

  • C++
// Created by WXX on 2021/2/26 20:28
#include <iostream>
#include <sstream>

using namespace std;

const int N = 1010;

int n;
int q[N];
int f[N], g[N];  // f[i]: 以a[i]结尾的LIS长度；g: 当前已经创建的递增子序列的结尾的数

int main() {

    // 没给数据总个数，读取输入有两种方式
    // 方式一
    string line;
    getline(cin, line);
    stringstream ssin(line);
    while (ssin >> q[n]) n++;
//    // 方式二
//    while (cin >> q[n]) n++;

    // 第一问
    int res = 0;
    for (int i = 0; i < n; i++) {
        f[i] = 1;
        for (int j = 0; j < i; j++)
            if (q[j] >= q[i])
                f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
    }
    cout << res << endl;

    // 第二问
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        int k = 0;
        while (k < cnt && g[k] < q[i]) k++;  // g是严格增的数据，找到大于等于q[i]的最小的数
        g[k] = q[i];
        if (k >= cnt) cnt++;
    }
    cout << cnt << endl;
    return 0;
}
  • Java 
import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
 * Created by WXX on 2021/2/26 21:41
 */
public class Main {

    public static final int N = 1010;

    static int n;
    static int[] q = new int[N];
    static int[] f = new int[N], g = new int[N];  // f[i]: 以a[i]结尾的LIS长度；g: 当前已经创建的递增子序列的结尾的数

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] t = br.readLine().split(" ");
        n = t.length;
        for (int i = 0; i < n; i++) q[i] = Integer.parseInt(t[i]);

        // 第一问
        int res = 0;
        for (int i = 0; i < n; i++) {
            f[i] = 1;
            for (int j = 0; j < i; j++)
                if (q[j] >= q[i])
                    f[i] = Math.max(f[i], f[j] + 1);
            res = Math.max(res, f[i]);
        }
        System.out.println(res);

        // 第二问
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            int k = 0;
            while (k < cnt && g[k] < q[i]) k++;  // g是严格增的数据，找到大于等于q[i]的最小的数
            g[k] = q[i];
            if (k >= cnt) cnt++;
        }
        System.out.println(cnt);
    }
}

AcWing 187. 导弹防御系统

问题描述

image-20210226143713314.png

分析

代码

  • C++
// Created by WXX on 2021/2/26 22:05
#include <iostream>

using namespace std;

const int N = 55;

int n;
int q[N];
int up[N], down[N];  // up: 当前已经创建的上升子序列的结尾的数；down: ...下降...
int ans;

// 遍历到q[u]，此时上升子序列个数为su个(up[0..su-1])，下降子序列有sd个(down[0..sd-1])
void dfs(int u, int su, int sd) {
    if (su + sd >= ans) return;
    if (u == n) {
        ans = su + sd;
        return;
    }

    // 情况1：将当前数放到上升子序列中
    int k = 0;
    while (k < su && up[k] >= q[u]) k++;  // up是非上升数组，寻找up中小于q[u]的最大的数
    int t = up[k];
    up[k] = q[u];
    if (k < su) dfs(u + 1, su, sd);
    else dfs(u + 1, su + 1, sd);
    up[k] = t;

    // 情况2：将当前数放入下降子序列中
    k = 0;
    while (k < sd && down[k] <= q[u]) k++;  // up是非下降数组，寻找down中大于q[u]的最小的数
    t = down[k];
    down[k] = q[u];
    if (k < sd) dfs(u + 1, su, sd);
    else dfs(u + 1, su, sd + 1);
    down[k] = t;
}

int main() {

    while (cin >> n, n) {
        for (int i = 0; i < n; i++) cin >> q[i];

        ans = n;  // 最差情况每个数是一个子序列
        dfs(0, 0, 0);

        cout << ans << endl;
    }
    return 0;
}
  • Java 
import java.util.Scanner;

/**
 * Created by WXX on 2021/2/26 22:33
 */
public class Main {

    public static final int N = 55;

    static int n;
    static int[] q = new int[N];
    static int[] up = new int[N], down = new int[N];
    static int ans;

    // 遍历到q[u]，此时上升子序列个数为su个(up[0..su-1])，下降子序列有sd个(down[0..sd-1])
    private static void dfs(int u, int su, int sd) {
        if (su + sd >= ans) return;
        if (u == n) {
            ans = su + sd;
            return;
        }

        // 情况1：将当前数放到上升子序列中
        int k = 0;
        while (k < su && up[k] >= q[u]) k++;  // up是非上升数组，寻找up中小于q[u]的最大的数
        int t = up[k];
        up[k] = q[u];
        if (k < su) dfs(u + 1, su, sd);
        else dfs(u + 1, su + 1, sd);
        up[k] = t;

        // 情况2：将当前数放入下降子序列中
        k = 0;
        while (k < sd && down[k] <= q[u]) k++;  // up是非下降数组，寻找down中大于q[u]的最小的数
        t = down[k];
        down[k] = q[u];
        if (k < sd) dfs(u + 1, su, sd);
        else dfs(u + 1, su, sd + 1);
        down[k] = t;
    }

    public static void main(String[] args) {

        Scanner sn = new Scanner(System.in);
        while ((n = sn.nextInt()) != 0) {
            for (int i = 0; i < n; i++) q[i] = sn.nextInt();

            ans = n;  // 最差情况每个数是一个子序列
            dfs(0, 0, 0);

            System.out.println(ans);
        }
    }
}

AcWing 314 低买

问题描述

image-20210302115647113.png

分析

  • 这一题的本质是求不同的下降子序列的个数。

  • 我们可以使用另外一个数组g记录不同下降子序列的个数，g[j]表示以a[j]结尾的不同的最长下降子序列的个数，如果后面仍然存在以a[j]结尾（即数组中存在相同元素，值都为a[j]，只保留最后一个a[j]对应的g[j]，其余的都置为0）的最长下降子序列，则将前面相同的g[j]置为0，防止重复计算相同的下降子序列。

  • 最后遍历g数组，统计出不同最长下降子序列的个数即可

image-20210302140944951.png

代码

  • C++
// Created by WXX on 2021/3/2 14:10
#include <iostream>

using namespace std;

const int N = 5010;

int n;
int a[N];
// f[i]表示以a[i]结尾的LDS的长度，g[j]表示以a[j]结尾的不同的LDS的个数
int f[N], g[N];

int main() {

    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

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

        for (int j = 1; j < i; j++)
            if (a[j] == a[i] && f[j] == f[i]) g[j] = 0;
            else if (a[j] > a[i] && f[j] + 1 == f[i]) g[i] += g[j];
        if (f[i] == 1) g[i] = 1;  // f[i]为1，说明其大于等于前面的所有元素，所以g[i]=1
//        if (g[i] == 0) g[i] = 1;  // 上面的语句换成这一句也行
    }

    int cnt = 0;
    for (int i = 1; i <= n; i++)
        if (f[i] == maxv) cnt += g[i];

    printf("%d %d\n", maxv, cnt);
    return 0;
}
  • Java
import java.util.Scanner;

/**
 * Created by WXX on 2021/3/2 14:45
 */
public class Main {

    public static final int N = 5010;

    static int n;
    static int[] a = new int[N];
    // f[i]表示以a[i]结尾的LDS的长度，g[j]表示以a[j]结尾的不同的LDS的个数
    static int[] f = new int[N], g = new int[N];

    public static void main(String[] args) {

        Scanner sn = new Scanner(System.in);
        n = sn.nextInt();
        for (int i = 1; i <= n; i++) a[i] = sn.nextInt();

        int maxv = 0;
        for (int i = 1; i <= n; i++) {
            f[i] = 1;
            for (int j = 1; j < i; j++)
                if (a[j] > a[i])
                    f[i] = Math.max(f[i], f[j] + 1);
            maxv = Math.max(maxv, f[i]);

            for (int j = 1; j < i; j++)
                if (a[j] == a[i] && f[j] == f[i]) g[j] = 0;
                else if (a[j] > a[i] && f[j] + 1 == f[i]) g[i] += g[j];
            if (g[i] == 0) g[i] = 1;  // 说明以a[i]结尾的LDS长度为1
        }
        int cnt = 0;
        for (int i = 1; i <= n; i++)
            if (f[i] == maxv) cnt += g[i];

        System.out.println(maxv + " " + cnt);
    }
}

三. LCS扩展题

AcWing 902. 最短编辑距离

问题描述

image-20210226122610085.png

分析

image-20210227111144328.png

代码

  • C++
// Created by WXX on 2021/2/27 11:13
#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
char a[N], b[N];
int f[N][N];

int main() {

    scanf("%d%s", &n, a + 1);  // 会用到下标i-1，因此字符串从1开始
    scanf("%d%s", &m, b + 1);

    // 初始化
    for (int j = 0; j <= m; j++) f[0][j] = j;  // 将空字符串变为b[1~j]需要j步添加操作
    for (int i = 0; i <= n; i++) f[i][0] = i;  // 将a[1~i]变为空字符串需要i步删除操作

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
            if (a[i] == b[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]);
            else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
        }
    printf("%d\n", f[n][m]);
    return 0;
}
  • Java 
import java.util.Scanner;

/**
 * Created by WXX on 2021/2/27 11:20
 */
public class Main {

    public static final int N = 1010;

    static int n, m;
    static char[] a, b;
    static int[][] f = new int[N][N];

    public static void main(String[] args) {

        Scanner sn = new Scanner(System.in);
        n = sn.nextInt();
        String s1 = " " + sn.next(); a = s1.toCharArray();  // // 会用到下标i-1，因此字符串从1开始
        m = sn.nextInt();
        String s2 = " " + sn.next(); b = s2.toCharArray();

        // 初始化
        for (int j = 0; j <= m; j++) f[0][j] = j;  // 将空字符串变为b[1~j]需要j步添加操作
        for (int i = 0; i <= n; i++) f[i][0] = i;  // 将a[1~i]变为空字符串需要i步删除操作

        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                f[i][j] = Math.min(f[i - 1][j] + 1, f[i][j - 1] + 1);
                if (a[i] == b[j]) f[i][j] = Math.min(f[i][j], f[i - 1][j - 1]);
                else f[i][j] = Math.min(f[i][j], f[i - 1][j - 1] + 1);
            }
        System.out.println(f[n][m]);
    }
}

AcWing 899. 编辑距离

问题描述

image-20210226122701337.png

分析

代码

  • C++
// Created by WXX on 2021/2/27 11:30
#include <iostream>
#include <cstring>

using namespace std;

const int N = 15, M = 1010;

int n, m;
int f[N][N];
char str[M][N];

int edit_distance(char a[], char b[]) {

    int la = strlen(a + 1), lb = strlen(b + 1);

    for (int j = 1; j <= lb; j++) f[0][j] = j;
    for (int i = 1; i <= la; i++) f[i][0] = i;

    for (int i = 1; i <= la; i++)
        for (int j = 1; j <= lb; j++) {
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
            if (a[i] == b[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]);
            else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
        }
    return f[la][lb];
}

int main() {

    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%s", str[i] + 1);

    while (m--) {
        char s[N];
        int limit;
        scanf("%s%d", s + 1, &limit);

        int res = 0;
        for (int i = 0; i < n; i++)
            if (edit_distance(str[i], s) <= limit)
                res++;

        printf("%d\n", res);
    }
    return 0;
}
  • Java 
import java.util.Scanner;

/**
 * Created by WXX on 2021/2/27 11:39
 */
public class Main {

    public static final int N = 15, M = 1010;

    static int n, m;
    static int[][] f = new int[N][N];
    static char[][] str = new char[M][];

    private static int editDistance(char[] a, char[] b) {

        int la = a.length - 1, lb = b.length - 1;

        for (int j = 1; j <= lb; j++) f[0][j] = j;
        for (int i = 1; i <= la; i++) f[i][0] = i;

        for (int i = 1; i <= la; i++)
            for (int j = 1; j <= lb; j++) {
                f[i][j] = Math.min(f[i - 1][j] + 1, f[i][j - 1] + 1);
                if (a[i] == b[j]) f[i][j] = Math.min(f[i][j], f[i - 1][j - 1]);
                else f[i][j] = Math.min(f[i][j], f[i - 1][j - 1] + 1);
            }
        return f[la][lb];
    }

    public static void main(String[] args) {

        Scanner sn = new Scanner(System.in);
        n = sn.nextInt(); m = sn.nextInt();
        for (int i = 0; i < n; i++) {
            String t = " " + sn.next();
            str[i] = t.toCharArray();
        }

        while (m-- != 0) {
            char[] s = (" " + sn.next()).toCharArray();
            int limit = sn.nextInt();

            int res = 0;
            for (int i = 0; i < n; i++)
                if (editDistance(str[i], s) <= limit)
                    res++;

            System.out.println(res);
        }
    }
}

四. LIS和LCS综合扩展题

AcWing 272. 最长公共上升子序列

问题描述

image-20210226143751178.png

分析

image-20210227153411347.png

代码

  • C++
// Created by WXX on 2021/2/27 15:02
#include <iostream>

using namespace std;

const int N = 3010;

int n;
int a[N], b[N];
int f[N][N];

// 此代码超时，需要优化，会出现 TLE
int main() {

    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 0; i <= n; i++) scanf("%d", &b[i]);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            f[i][j] = f[i - 1][j];
            if (a[i] == b[j]) {
                f[i][j] = max(f[i][j], 1);
                for (int k = 1; k < j; k++)  // 找到1~k-1中满足 b[k] < a[i] 的最大的f[i-1][k]
                    if (b[k] < b[j])  // 因为a[i] == b[j]，所以改写为 if (b[k] < a[i])
                        f[i][j] = max(f[i][j], f[i - 1][k] + 1);
            }
        }

    int res = 0;
    for (int i = 1; i <= n; i++) res = max(res, f[n][i]);

    printf("%d\n", res);

    return 0;
}
  • Java 
/**
 * Created by WXX on 2021/2/27 15:39
 * 未超时，可以AC
 */
public class Main {

    public static final int N = 3010;

    static int n;
    static int[] a = new int[N], b = new int[N];
    static int[][] f = new int[N][N];

    public static void main(String[] args) {

        Scanner sn = new Scanner(System.in);
        n = sn.nextInt();
        for (int i = 1; i <= n; i++) a[i] = sn.nextInt();
        for (int i = 1; i <= n; i++) b[i] = sn.nextInt();

        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) {
                f[i][j] = f[i - 1][j];
                if (a[i] == b[j]) {
                    f[i][j] = Math.max(f[i][j], 1);
                    for (int k = 1; k < j; k++)
                        if (b[k] < b[j])
                            f[i][j] = Math.max(f[i][j], f[i - 1][k] + 1);
                }
            }

        int res = 0;
        for (int i = 1; i <= n; i++) res = Math.max(res, f[n][i]);

        System.out.println(res);
    }
}

代码优化（只用C++演示）

  • 因为 $a[i]==b[j]$，所以可以将C++中的的三重循环改为如下代码：

c++ for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { f[i][j] = f[i - 1][j]; if (a[i] == b[j]) { f[i][j] = max(f[i][j], 1); for (int k = 1; k < j; k++) // 找到1~k-1中满足 b[k] < a[i] 的最大的f[i-1][k] if (b[k] < a[i]) // 因为a[i] == b[j]，所以改写为 if (b[k] < a[i]) f[i][j] = max(f[i][j], f[i - 1][k] + 1); } }

  • 此时考虑第三重循环的含义：找到1~k-1中满足 b[k] < a[i] 的最大的f[i-1][k]。在固定第一重循环变量 i 时，a[i]是定值，第二重循环相当于每次增加一个数据，然后求最大值，因此可以用一个变量记录前缀的最大值。

image-20210227155524951.png

因此优化后的代码如下：

// Created by WXX on 2021/2/27 15:30
#include <iostream>

using namespace std;

const int N = 3010;

int n;
int a[N], b[N];
int f[N][N];

int main() {

    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 0; i <= n; i++) scanf("%d", &b[i]);

    for (int i = 1; i <= n; i++) {
        int maxv = 1;  // 表示 f[i-1][k] 满足 b[k] < a[i] 的最大值，k=1,2,...j-1
        for (int j = 1; j <= n; j++) {
            f[i][j] = f[i - 1][j];
            if (a[i] == b[j])f[i][j] = max(f[i][j], maxv);
            if (b[j] < a[i]) maxv = max(maxv, f[i - 1][j] + 1);
        }
    }

    int res = 0;
    for (int i = 1; i <= n; i++) res = max(res, f[n][i]);

    printf("%d\n", res);

    return 0;
}

LeetCode上一些相关问题

Leetcode 0300 最长上升子序列

问题描述

image-20210227164120195.png

分析

  • 典型的LIS问题

代码

  • C++
/**
 * 执行用时：344 ms, 在所有 C++ 提交中击败了40.59%的用户
 * 内存消耗：10.3 MB, 在所有 C++ 提交中击败了66.35%的用户
 */
class Solution {
public:
    int lengthOfLIS(vector<int> &nums) {

        int n = nums.size();
        int res = 1;
        vector<int> f(n);
        for (int i = 0; i < n; i++) {
            f[i] = 1;
            for (int j = 0; j < i; j++)
                if (nums[i] > nums[j])
                    f[i] = max(f[i], f[j] + 1);
            res = max(res, f[i]);
        }
        return res;
    }
};

/**
 * 执行用时：12 ms, 在所有 C++ 提交中击败了89.97%的用户
 * 内存消耗：10.2 MB, 在所有 C++ 提交中击败了70.59%的用户
 */
class Solution {
public:
    int lengthOfLIS(vector<int> &nums) {

        vector<int> q;  // q[k]表示长度为k的上升子序列的结尾最小值
        for (auto x : nums) {
            if (q.empty() || x > q.back()) q.push_back(x);
            else {
                if (x <= q[0]) q[0] = x;
                else {
                    // 找到小于x最大的数据
                    int l = 0, r = q.size() - 1;
                    while (l < r) {
                        int mid = l + r + 1 >> 1;
                        if (q[mid] < x) l = mid;
                        else r = mid - 1;
                    }
                    q[r + 1] = x;
                }
            }
        }
        return q.size();
    }
};
  • Java
/**
 * 执行用时：71 ms, 在所有 Java 提交中击败了70.29%的用户
 * 内存消耗：38.2 MB, 在所有 Java 提交中击败了21.50%的用户
 */
public class Solution3 {
    public int lengthOfLIS(int[] nums) {

        int n = nums.length;
        int res = 1;
        int[] f = new int[n];
        for (int i = 0; i < n; i++) {
            f[i] = 1;
            for (int j = 0; j < i; j++)
                if (nums[i] > nums[j])
                    f[i] = Math.max(f[i], 1 + f[j]);
            res = Math.max(res, f[i]);
        }
        return res;
    }
}

/**
 * 执行用时：8 ms, 在所有 Java 提交中击败了77.78%的用户
 * 内存消耗：38.1 MB, 在所有 Java 提交中击败了31.84%的用户
 */
public class Solution {
    public int lengthOfLIS(int[] nums) {

        List<Integer> q = new ArrayList<>();
        for (int x : nums) {
            if (q.isEmpty()  || x > q.get(q.size() - 1)) q.add(x);
            else {
                if (x <= q.get(0)) q.set(0, x);
                else {
                    // 找到小于x最大的数据
                    int l = 0, r = q.size() - 1;
                    while (l < r) {
                        int mid = l + r + 1 >> 1;
                        if (q.get(mid) < x) l = mid;  // 说明nums[mid] < x, nums[mid]是待选数据
                        else r = mid - 1;
                    }
                    q.set(r + 1, x);
                }
            }
        }
        return q.size();
    }
}

Leetcode 0334 递增的三元子序列

问题描述

image-20210227164904231.png

分析

  • 直接使用LIS II中的方法即可，因为只需要判断是否存在长度为3的递增子序列，因此直接遍历即可，不需要二分。

代码

  • C++
/**
 * 执行用时：8 ms, 在所有 C++ 提交中击败了68.13%的用户
 * 内存消耗：10.1 MB, 在所有 C++ 提交中击败了48.16%的用户
 */
class Solution {
public:
    bool increasingTriplet(vector<int> &nums) {
        vector<int> q(2, INT_MAX);
        for (auto a : nums) {
            int k = 2;
            while (k > 0 && q[k - 1] >= a) k--;
            if (k == 2) return true;
            q[k] = a;
        }
        return false;
    }
};
  • Java
/**
 * 执行用时：1 ms, 在所有 Java 提交中击败了51.05%的用户
 * 内存消耗：38.4 MB, 在所有 Java 提交中击败了22.57%的用户
 */
public class Solution {
    public boolean increasingTriplet(int[] nums) {

        int[] q = new int[2];
        Arrays.fill(q, Integer.MAX_VALUE);
        for (int x : nums) {
            int k = 2;
            while (k > 0 && q[k - 1] >= x) k--;  // 找到小于x的最大的数
            if (k == 2) return true;
            q[k] = x;
        }
        return false;
    }
}

Leetcode 0673 最长递增子序列的个数

问题描述

image-20210302151523073.png

分析

  • 这一题和 AcWing 314 低买 十分类似，不同点是这一题重复的序列也要计算上，从这点来说，这个题目变得更加的容易了。

  • 我们仍然使用数组g记录方案数，g[i]表示所有以a[i]结尾的LIS的结果的个数（可以存在相同的LIS）。然后我们根据f进行分类讨论即可（其中0<=j<i）：

（1）如果 $f[i]<f[j]+1$ ，则 $g[i]=g[j]$；

（2）如果 $f[i]==f[j]+1$ ，则 $g[i]+=g[j]$；

代码

  • C++
/**
 * 执行用时：188 ms, 在所有 C++ 提交中击败了28.31%的用户
 * 内存消耗：12.8 MB, 在所有 C++ 提交中击败了86.53%的用户
 */
class Solution {
public:
    int findNumberOfLIS(vector<int> &nums) {
        int n = nums.size();
        vector<int> f(n), g(n);

        int maxv = 0, cnt = 0;
        for (int i = 0; i < n; i++) {
            f[i] = g[i] = 1;
            for (int j = 0; j < i; j++)
                if (nums[j] < nums[i]) {
                    if (f[i] < f[j] + 1) f[i] = f[j] + 1, g[i] = g[j];
                    else if (f[i] == f[j] + 1) g[i] += g[j];
                }
            if (maxv < f[i]) maxv = f[i], cnt = g[i];
            else if (maxv == f[i]) cnt += g[i];
        }
        return cnt;
    }
};
  • Java
/**
 * Created by WXX on 2021/3/2 15:08
 * 执行用时：23 ms, 在所有 Java 提交中击败了93.39%的用户
 * 内存消耗：37.9 MB, 在所有 Java 提交中击败了92.39%的用户
 */
public class Solution {

    public int findNumberOfLIS(int[] nums) {

        int n = nums.length;
        int[] f = new int[n], g = new int[n];

        int maxv = 0, cnt = 0;
        for (int i = 0; i < n; i++) {
            f[i] = g[i] = 1;
            for (int j = 0; j < i; j++)
                if (nums[j] < nums[i]) {
                    if (f[i] < f[j] + 1) {
                        f[i] = f[j] + 1; g[i] = g[j];
                    } else if (f[i] == f[j] + 1) g[i] += g[j];
                }
            if (maxv < f[i]) {
                maxv = f[i]; cnt = g[i];
            } else if (maxv == f[i]) cnt += g[i];
        }
        return cnt;
    }
}

Leetcode 1143 最长公共子序列

问题描述

image-20210227170611398.png

分析

  • 典型的LCS问题

代码

  • C++
/**
 * 执行用时：32 ms, 在所有 C++ 提交中击败了32.10%的用户
 * 内存消耗：12.6 MB, 在所有 C++ 提交中击败了54.01%的用户
 */
class Solution {
public:
    int longestCommonSubsequence(string a, string b) {

        int n = a.size(), m = b.size();
        a = ' ' + a; b = " " + b;

        vector<vector<int>> f(n + 1, vector<int>(m + 1));
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                f[i][j] = max(f[i - 1][j], f[i][j - 1]);
                if (a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
            }
        return f[n][m];
    }
};
  • Java
/**
 * 执行用时：10 ms, 在所有 Java 提交中击败了80.02%的用户
 * 内存消耗：42.4 MB, 在所有 Java 提交中击败了27.03%的用户
 */
public class Solution2 {
    public int longestCommonSubsequence(String text1, String text2) {

        int n = text1.length(), m = text2.length();
        char[] a = (" " + text1).toCharArray(), b = (" " + text2).toCharArray();

        int[][] f = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
                if (a[i] == b[j]) f[i][j] = Math.max(f[i][j], f[i - 1][j - 1] + 1);
            }
        return f[n][m];
    }
}

NowCoder上一些相关习题

NC92 最长公共子序列

问题描述

image-20210303003044043.png

分析

  • 根据状态转移方程反推即可

代码

  • C++
class Solution {
public:
    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    string LCS(string s1, string s2) {

        int n = s1.size(), m = s2.size();
        vector<vector<int>> f(n + 1, vector<int>(m + 1, 0));
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                f[i][j] = max(f[i][j - 1], f[i - 1][j]);
                if (s1[i - 1] == s2[j - 1]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
            }

        if (f[n][m] == 0) return "-1";
        string res;
        int i = n, j = m;
        while (f[i][j]) {
            while (f[i][j] == f[i - 1][j]) i--;
            while (f[i][j] == f[i][j - 1]) j--;
            res += s1[i - 1];
            i--, j--;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

0 评论