先看題目
題目描述
給出1-n的兩個排列P1和P2,求它們的最長公共子序列。
輸入輸出格式
輸入格式:
第一行是一個數n,
接下來兩行,每行為n個數,為自然數1-n的一個排列。
輸出格式:
一個數,即最長公共子序列的長度
輸入輸出樣例
輸入樣例#1:
5
3 2 1 4 5
1 2 3 4 5
輸出樣例#1:
3
再看看是如何轉換的
因為兩個序列内容一樣隻是元素位置不一樣,是以可以把序列A的元素在序列B中的位置用C[]記錄下來,比如
A:3 2 1 4 5
B:4 5 1 2 3
C:5 4 3 1 2
也可以這麼說
A=B[5] B[4] B[3] B[1] B[2]
C相當于一個指針數組或者說密碼本,從B中可以解讀出A
轉了之後有什麼規律呢?
Ci對應Ai,C的子序列一定是A的子序列
比如 C[1] C[2] 對應 A[1] A[2]
Ai=B(Ci) 相當于複合函數
B把C映射成了A,但Ai就是Ci這個位置沒變不會交錯(C1對應A2,沒有這種情況)
是以C的子序列一定是A的子序列
Ci<Cj這兩個元素在B中是一個子序列
比如 C[4],C[5]對應 1 2 對應B[1] B[2] ,B[1] B[2]是B的一個子序列
C中,若Cj>Ci(j>i)這兩個元素既是A的子序列,也是B的子序列
這樣,我們要找的從兩個序列的最長公共子序列變成了尋找C的某個子序列,
這裡記為K,而且K1<K2<K3....這樣才能保證既是A的子序列,又是B的子序列
也就是最長公共子序列
這樣C中的LIS答案就是A與B的LCS答案
參考:https://pks-loving.blog.luogu.org/junior-dynamic-programming-dong-tai-gui-hua-chu-bu-ge-zhong-zi-xu-lie