动态规划LIS模型

1. LIS 模型

LIS问题：给定一个长度为N的数列 a，求数值严格单调递增的子序列的长度最长是多少。

算法思想：

• 状态表示：$f[i]$表示由数列$a$的前$i$个数字组成（不一定包含所有数字）且以$a[i]$结尾的最长上升子序列的长度。
• 状态计算：遍历小于$i$的每一个$j$，若有$a[j] < a[i]$，则$f[i] = max(f[i], f[j] + 1)$，否则$f[i] = 1$。

代码实现：

import java.util.*;

public class Main {
    static final int N = 1010;
    static int[] a = new int[N], f = new int[N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 1; i <= n; i ++) a[i] = sc.nextInt();
        for (int i = 1; i <= n; i ++) {
            f[i] = 1;
            for (int j = 1; j <= n; 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);
    }
}

优化：
在状态计算那一步，我们每次去遍历所有小于$i$的$j$，这样显然时间复杂度是$O(n^2)$。对于数据量大的题目，是会$TLE$的。我们可以使用贪心的方式来优化，具体如下：
我们用一个数组$q$来维护当前遍历到的元素之前的序列，每次遍历到一个元素$a[i]$，就在$q$中寻找小于$a[i]$的最大的元素$q[r]$，并将$q[r+1]$赋值为$a[i]$，同时更新一下最长上升子序列的长度。
有三个注意点：

• 将$q[r+1]$赋值为$a[i]$：有可能$a[i]$就是维护的序列中最大的元素，因此会是添加到序列后面。也有可能是将$q[r+1]$修改为$a[i]$。
• 如果是将$q[r+1]$修改为$a[i]$，这个操作是不影响后面的遍历的，因为如果后面某个元素$a[j]$能放到原来的$q[r+1]$后面，也必然能放到新的$q[r+1](a[i])$后面（因为当前的$q[r+1]$必然是大于$a[i]$的）。
• 在该序列中寻找小于$a[i]$的最大的元素$q[r]$：这个操作我们可以通过二分来实现。

优化代码实现：

import java.io.*;

public class Main {
    static final int N = 100010;
    static int[] a = new int[N], q = new int[N];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] s = br.readLine().split(" ");
        for (int i = 0; i < n; i ++) a[i] = Integer.parseInt(s[i]);
        
        int len = 0;
        q[0] = -(int)2e9;
        for (int i = 0; i < n; i ++) {
            int l = 0, r = len;
            while(l < r) {
                int mid = l + r + 1 >> 1;
                if (q[mid] < a[i]) l = mid;
                else r = mid - 1;
            }
            // 更新最长上升子序列长度（不一定能更新）
            len = Math.max(len, r + 1);
            // 将新点插入
            q[r + 1] = a[i];
        }
        System.out.print(len);
    }
}

LIS模型相关题目：

• AcWing 1017. 怪盗基德的滑翔翼：题目需要求从一个点开始，每一次的下一个位置不许严格低于前一个位置，问最远能走多远。逆向思维，求一遍LIS问题即可。
• AcWing 482. 合唱队形：题目要求至少要多少名同学出列才能形成合唱队形，我们可以求合唱队形最长能多长（即正反分别求一次LIS问题），然后用总人数减去最长合唱队行人数。
• AcWing 1016. 最大上升子序列和：LIS问题求的是数量，而这道题求的是每个元素的和，所以求LIS问题时将+1改为+a[i]即可。
• AcWing 187. 导弹防御系统：这道题虽然也是LIS模型，但是已经跟DP无关了，解题方法为DFS+贪心版LIS。
  

2. LCS模型

LCS问题：给定两个长度分别为n 和 m 的字符串 a 和 b，求既是 a 的子序列又是 b 的子序列的字符串长度最长是多少。

算法思想：

• 状态表示：$f[i][j]$表示由数列$a$的前$i$个数字与数列$b$的前$j$个数字组成的公共子序列的长度最大值。
• 状态计算：
  • 当包含$a[i]$且不包含$b[j]$时，$f[i][j] = max(f[i][j], f[i][j - 1])$；
  • 当包含$b[j]$且不包含$a[i]$时，$f[i][j] = max(f[i][j], f[i - 1][j])$；
  • 当既不包含$a[i]$也不包含$b[j]$时，$f[i][j] = max(f[i][j], f[i - 1][j - 1])$，但是这种情况可以被以上任意一种包含；
  • 当包含$a[i]$且包含$b[j]$时（要求$a[i] = b[j]$），$f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1)$。

代码实现：

import java.util.*;

public class Main {
    static final int N = 1010;
    static int[][] f = new int[N][N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        char[] a = (" " + sc.next()).toCharArray(), b = (" " + sc.next()).toCharArray();
        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= m; j ++) {
                f[i][j] = Math.max(f[i][j - 1], f[i - 1][j]);
                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]);
    }
}

3. LCIS模型

LCIS问题：给定两个长度分别为n 和 m 的字符串 a 和 b，求既是 a 的子序列又是 b 的子序列且数值严格单调递增的字符串长度最长是多少。

算法思想：

• 状态表示：$f[i][j]$表示由数列$a$的前$i$个数字与数列$b$的前$j$个数字组成且以$b[j]$结尾的最长上升公共子序列的长度的最大值。
• 状态计算：
  • 当不包含$a[i]$时，$f[i][j] = f[i - 1][j]$；
  • 当包含$a[i]$时（要求$a[i] = b[j]$），此时$f[i][j]$起码为1，$f[i][j] = max(f[i][j], 1)$，然后遍历$b[j]$之前的元素，若$b[k]<b[j]$，则$f[i][j] = max(f[i][j], f[i][k] + 1)$。

代码实现：

import java.util.*;

public class Main {
    static final int N = 3010;
    static int[] a = new int[N], b = new int[N];
    static int[][] f = new int[N][N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 1; i <= n; i ++) a[i] = sc.nextInt();
        for (int i = 1; i <= n; i ++) b[i] = sc.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][k] + 1);
                }
            }
        int res = 0;
        for (int i = 1; i <= n; i ++) res = Math.max(res, f[n][i]);
        System.out.println(res);
    }
}

优化：
上述的方法时间复杂度达到了$O(n^3)$，数据量稍大一些就$TLE$。我们可以对代码做等价变形优化成$O(n^2)$。
可以发现，当$a[i] = b[j]$时，if (b[k] < b[j]) f[i][j] = Math.max(f[i][j], f[i][k] + 1);这一句等价于if (b[k] < a[i]) f[i][j] = Math.max(f[i][j], f[i][k] + 1);，我们就能发现，这一部分求解其实是与$b[j]$无关的。我们可以直接用一个变量代替这一部分，每次循环$j$时维护起来即可。
优化代码实现：

import java.util.*;

public class Main {
    static final int N = 3010;
    static int[] a = new int[N], b = new int[N];
    static int[][] f = new int[N][N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 1; i <= n; i ++) a[i] = sc.nextInt();
        for (int i = 1; i <= n; i ++) b[i] = sc.nextInt();
        for (int i = 1; i <= n; i ++) {
            int maxv = 1;
            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], maxv);
                // 这里的b[j]就等价于优化前的b[k]，a[i]就等价于优化前的b[j]
                if (a[i] > b[j]) maxv = Math.max(maxv, f[i][j] + 1);
            }
        }
        int res = 0;
        for (int i = 1; i <= n; i ++) res = Math.max(res, f[n][i]);
        System.out.println(res);
    }
}