首先，我對LCS與LIS並沒有深入理解，是請教 Lanstar 高手，再自行輔以「演算法筆記」與「網路文章」… 等等 實作成功，因此如果有些觀念理解有誤，還請不吝指教

LCS

• • LCS的全名是Longest Common Subequence，「最長 共同 子序列」，
    也就是兩個字串間，相似度為何，共同擁有的連續字串有哪些
  • 通常會使用DP來解決，並搭配len(s1)*len(s2)的表格，因此複雜度大概會是O(N^2)

LCS實作參考影片：

• Longest Common Subsequence(LCS)問題的演算法介紹

LIS

• • LIS的全名是Longest Increasing Subsequence，「最長 遞增 子序列」，
    只要子序列一直往上增加，就可以了！
  • 然而LCS的題目，可以改以LIS來解決，這題就是這麼一個範例，
    而LIS的複雜度是O(N logN)，差別非常大！
  • 原理大概是O(logN)的二分搜尋法，乘上迴圈O(N)。
    LCS轉換LIS難度在於前處理，LIS本身的程式碼也是很簡潔！

LCS轉LIS、LIS本身實作參考資料：

• 程式碼實作：演算法筆記 Longest Increasing Subsequence: Robinson-Schensted-Knuth Algorithm
• 演算法知識 - Longest Common Subsequence 最長共同子序列(時間複雜度 O(nlogn))
• 演算法知識 - Longest Increasing Subsequence 最長遞增子序列(時間複雜度 O(nlogn) 與 時間複雜度 O(n^2))
• Longest Increasing Subsequence (最長遞增子序列)