題目鏈接：
https://vjudge.net/problem/UVA-12511
題目大意：
給定兩個序列，求出兩個序列的最長公共上升子序列（嚴格上升）。
解題過程：
比賽的時候沒有做出來，非常咸魚的一場比賽，當時是想錯了狀態。當時想的狀態是定義dp[i][j]，意味以第一個串第前i個元素，第二個串前j個元素的最長公共上升子序列長度。
但是這樣定義狀態有后效性，比如當前我知道dp[i][j]要以這個狀態進行轉移的話，需要他是以那個狀態轉移而來的，換句話說，我轉移的時候要知道他是以前j個數中那一個結尾的。
如果換一種方式，dp[i][j]代表以第一個序列前i個元素并且以第i個結束，第二個序列前j個元素并且以第j個元素結尾的最長上升子序列的長度。
這樣加入的限制太多，不容易找出狀態轉移方程，或者轉移起來太麻煩。
題目分析：
這里以dp[i][j]表示第一個序列中前i個元素，第二個序列前j個元素并且以第j個元素為結尾的最長上升子序列。
這樣對比前兩種狀態表示方式有兩種好處，一是無后效性，dp[i][j]的第二維就確定了這個序列是以那一個元素結尾。二是容易進行轉移，對于dp[i][j]可由兩種方式轉移而來：
dp[i][j]={dp[i?1][j],max(dp[i?1][k])+1,a[i]≠b[i]k∈[1,j?1]∧b[k]<b[j]∧a[i]=b[i]
這里的k可以在循環中找出，時間復雜度為O(n2).
AC代碼：
#include <bits/stdc++.h>
using namespace std;const int MAX = 1123;int dp[MAX][MAX], a[MAX], b[MAX];int main() {int T;scanf("%d", &T);while (T--) {int n, m;scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);}scanf("%d", &m);for (int i = 1; i <= m; i++) {scanf("%d", &b[i]);}memset(dp, 0, sizeof(dp));for (int i = 1; i <= n; i++) {int maxn = 0;for (int j = 1; j <= m; j++) {//不相等時的轉移dp[i][j] = dp[i-1][j];//更新maxn變量，表示當前小于a[i]的dp[i-1][k]的最大值if (a[i] > b[j] && maxn < dp[i-1][j])maxn = dp[i-1][j];//相等的話if (a[i] == b[j])dp[i][j] = maxn+1;}}int ans = 0;for (int i = 1; i <= m; i++) {ans = max(ans, dp[n][i]);}printf("%d\n", ans);}
}
)
