10949 : Kids in a Grid ★★★★☆ 題組：Problem Set Archive with Online Judge 解題者：陳鵬宇 解題日期：2018年4月10日 題意：首先讀入測試的case數，在每個case中，有兩個小孩位於一個充滿字元的二維方格，給定兩人各自的起點與行走的方位(N,E,W,S)，一次僅能前進一格，並將經過格子中的字元記錄下來，形成兩個字串。 所求為:兩字串至少分別要刪去多少字元，方能使得兩字串刪減後相同(不可改變順序)，亦即:尋找最長共同子序列(Longest Common Subsequence , LCS)，並分別將刪去的最少字元數印出。

題意範例(一)： Input: output: 1 Case 1: 3 2 3 4 //case 1 //ABCDG刪去3個字元 ABCD //ADEB刪去2個字元 DEFG ABCD 4 1 1 EEES //起點(1,1) 走完結果 ABCDG 3 3 1 NES //起點(3,1) 走完結果 ADEB //LCS: AD 及 AB //亦即ABCDG刪去BCG 或 CDG // ADEB 刪去 EB 或 DE

題意範例(二)： Input: output: 1 Case 1: 6 9 6 3 //case 1 // AUAUAVAV刪去3個字元 U(/ // K\g!!!gEVAV刪去9個字元 AS< VLK Eg\ M!! {M+ 8 2 1 //起點(2,1) 走完結果 AUAUAVAVE NSNSSNSS 11 3 3 //起點(3,3) 走完結果 K\g!!!gEVAVL SWSEWNWNNSE //LCS: VAV //亦即:AUAUAVAV 刪去 AUAUAE // K\g!!!gEVAV 刪去 K\g!!!gEL

解法(一)： Hunt-Szymanski Algorithm:將LCS問題轉為二維LIS問題，再把二維LIS轉為一維LIS，並用LIS解之。 (* LIS : Longest Increasing Subsequence最長遞增序列) (如:5 1 3 6 2 8 4 9的LIS 為1 3 6 8 9) 若要尋找LIS的長度，有個好的演算法，稱作Robinson-Schensted-Knuth Algorithm，做法範例如下: 將輸入序列的開頭到結尾都掃過一遍，若目前數字大於目前LIS的最後一個數字，即放入後面，否則便要進行最佳化。 而把LCS轉為LIS的過程，是依序找string 1每個元素在string 2中對應到元素的所有位置，再把這些位置遞減排序後，此序列的LIS即為答案，也就是:把LCS的元素對應到的位置，排為一序列，解這個位置序列的LIS，就是LCS的答案。 此方法的時間複雜度為O(N*L)。 (N 為數列長度， L 為 LIS 的長度)

以上頁範例(5 1 3 6 2 8 4 9)來說，首先目前LIS為空，所以: 5: 5 > -INF ->目前LIS : 5 1: 1 < 5 ->找到>=1的最近位置 ->目前LIS : 1 3: 3 > 1 ->目前LIS : 1 3 6: 6 > 3 ->目前LIS : 1 3 6 2: 2 < 6 ->找到>=2的最近位置 ->目前LIS : 1 2 6 8: 8 > 6 ->目前LIS : 1 2 6 8 4: 4 < 6 ->找到>=4的最近位置 ->目前LIS : 1 2 4 8 9: 9>8 ->目前LIS : 1 2 4 8 9 ->得LIS長度為5 值得注意的是，此演算法僅能找到LIS的長度，並無法找出LIS內容為何(1 2 4 8 9 != 1 3 6 8 9)，使用時須注意。

解法範例： 令string 1 =cdacsbx , string 2 = bbdaxcbc 首先把string 2 中的字元分類，把同一個字元在string 2 中出現的所有位置記為一linked list: a:4 b:1 -> 2 -> 7 c:6 -> 8 d:3 x:5 接著依序比對string 1 中所有字元，並將對應到的字元位置以遞減排列，解出此數列的LIS，即為答案。 c d a c s b x 6 , 8, 3 , 4, 6 , 8, 1 ,2 ,7, 5 ->解 6 8 3 4 6 8 1 2 7 5的LIS，得LIS長度為4

解法(二)： 這是我初始的解法:以recursive的方法，設string 1中所有字元皆為”最長共同子序列”的開頭，向後尋找與string 2相符的所有字元，形成相符字串，其中最長的字串，即為所求”最長共同子序列” ，再將string 1& string 2的長度減去”最長共同子序列” 長度，即為輸出。 解法範例(二) ：

解法(二)缺點： 此解法雖能順利完成輸出，不過題目給定，兩個小孩最多能走20000步，也就是，兩字串string 1& string 2之長度最長能達到20000個字元，而這個方法將所有可能都檢查一次，時間複雜度為O(n^2)，n為字串長度，執行時間會超出限制的三秒，所以無法完整解決問題。

解法(三)： 自己的解法失敗後，我在網路上找到的兩個方法，其一是解法一，其二是這個: 用Dynamic Programming分析，令能找出string 1, string 2之LCS的function為f(string 1,string 2)，並將string 1與 string 2的最後一個字元分開(令其分別為a,b)，剩餘字串為substring 1, substring 2 。 考慮四種情況: (1) LCS包含a,b --f(string 1,string 2) = f(substring 1,substring 2) + a (2) LCS包含a,不包含b-- f(string 1,string 2) = f(string 1, substring 2) (3) LCS包含b,不包含a-- f(string 1,string 2) = f(substring 1, string 2) (4) LCS不包含a,也不包含b -- f(string 1,string 2) = f(substring 1, substring 2)

其後，建置一個二維陣列table，其長寬分別為string 1與 string 2的長度，陣列中的元素table[i][j]為string 1與 string 2的前i個字元與前j個字元所形成的子字串，所對應的LCS長度，建置過程中，依照先前所歸納出的原則: (1)若LCS包含string 1[i]與string 2[j] ，則LCS = f(substring 1,substring 2) + string 1[i] ，由於陣列中存的是LCS的長度，所以f(substring 1,substring 2) 的長度存在table[i-1][j-1]中， 也就是table[i][j] = table[i-1][j-1]+1 (2)若是其他情況 table[i][j] = max(table[i-1][j], table[i][j-1] , table[i-1][j-1]) = max(table[i-1][j], table[i][j-1]) 最後，最右下角的元素即為LCS之長度。 但此方法的時間複雜度仍為O(n^2)，亦不可解。

解法範例(三) ：

討論： (1) 由於網路上關於這題的範例極少，所以不知道還有沒有其他好的方法可解。 (2) 字串長度最長達20000，所以時間複雜度在O(n^2)以上的演算法恐怕很難在三秒內完成，但Hunt-Szymanski Algorithm是把LCS轉為二維LIS問題，再用Robinson-Schensted-Knuth Algorithm去解，但這只能找長度，如果要找出完整LCS字串，應該就無法在三秒內達成了。