AcWing 272. 最長公共上升子序列 (線性DP + 字首最值優化）

​​AcWing 272. 最長公共上升子序列​​

題目

名字就是題目，給出兩個序列A，B，求最長公共上升子序列。(n < 3e3)

分析

線性dp。

①： 狀态表示（經驗）

1. 集合： 表示所有在 和 中出現過，且最後以 的最長公共上升子序列的集合，
2. 屬性：表示集合中長度的最大值

②： 狀态轉移

1. 不包括 ，----->
2. 包括 （繼續劃分），枚舉符合條件的 (b[k] < b[j] && k < j) ---->

複雜度

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f;
const int N = 3e3 + 5;

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

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) 
    scanf("%d", &a[i]);
  for (int i = 1; i <= n; i++) 
    scanf("%d", &b[i]);
  for (int i = 1; i <= n; i++) 
    for (int j = 1; j <= n; j++) {
      dp[i][j] = dp[i-1][j];    // 不包含
      if (a[i] == b[j]) {     
        int maxv = 1;
        for (int k = 1; k < j; k++) 
          if (b[k] < b[j]) 
            maxv = max(maxv, dp[i-1][k] + 1);
        dp[i][j] = max(maxv, dp[i][j]);
      }
    }
  int res = 0;
  for (int i = 1; i <= n; i++)   // 答案枚舉一下
    res = max(res, dp[n][i]);
  printf("%d\n", res);
  return 0;
}      

優化

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f;
const int N = 3e3 + 5;

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

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) 
    scanf("%d", &a[i]);
  for (int i = 1; i <= n; i++) 
    scanf("%d", &b[i]);
  for (int i = 1; i <= n; i++) {
    int maxv = 1;
    for (int j = 1; j <= n; j++) {
      dp[i][j] = dp[i - 1][j];
      if (a[i] == b[j]) {
        dp[i][j] = max(maxv, dp[i][j]);
      }
      if (b[j] < a[i]) maxv = max(maxv, dp[i-1][j] + 1);
    }
  }
  int res = 0;
  for (int i = 1; i <= n; i++) 
    res = max(res, dp[n][i]);
  printf("%d\n", res);
  return 0;
}