线性DP

1. 线性DP

定义

• 这里的定义只是一个概述，所谓的线性DP是指我们的递推方程是存在一个线性的递推关系。可以是一维线性的、二维线性的、三维线性的、…

• 最长上升子序列模型属于线性DP。

2. AcWing上的线性DP题目

AcWing 898. 数字三角形

问题描述

• 问题链接：AcWing 898. 数字三角形

  

分析

代码

• C++

#include <iostream>

using namespace std;

const int N = 510;

int n;
int f[N][N];  // 最初存储的是三角形中的值

int main() {

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

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

    cout << f[1][1] << endl;

    return 0;
}

AcWing 895. 最长上升子序列

问题描述

• 问题链接：AcWing 895. 最长上升子序列

  

分析

代码

• 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);
    }
}

AcWing 896. 最长上升子序列 II

问题描述

• 问题链接：AcWing 896. 最长上升子序列 II

  

分析

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

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

知道了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\ast 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);
    }
}

AcWing 897. 最长公共子序列

问题描述

• 问题链接：AcWing 897. 最长公共子序列

  

分析

代码

• 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]);
    }
}

AcWing 902. 最短编辑距离

问题描述

• 问题链接：AcWing 902. 最短编辑距离

  

分析

代码

• 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. 编辑距离

问题描述

• 问题链接：AcWing 899. 编辑距离

  

分析

• 这一题就是AcWing 902. 最短编辑距离的一个简单应用，只不过需要多次计算编辑距离。

代码

• 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);
        }
    }
}