LCS and LIS (動態規劃經典問題)

LCS

CSDN。時間O(n2)，最好有O(nlogn)方法。空間可從二維變成兩個一維(一個紀錄上一次的，一個紀錄這一次的東西)。

題目：

Leetcode 1143 (模板題) : 題解。

AcWing 315 : 變化題，印出所有滿足長度的string。

UVA 111 (簡單題)

LIS

IT邦幫忙，只要記住O(nlogn)方法。

題目：這篇有Leetocde所有LIS題目總結

Leetcode 300 (模板題)

Leetcode 334 : LIS，但是可以更簡化，速度更快，因為他只要長度為3的字串。

Leetcode 354 : 先sort(長度按照小到大，長度一樣時，寬度大到小，避免同一長度選到兩個信封)，再LIS。

Leetcode 673 : 考LIS最長數列有幾個，用DP，DP[i]代表以位置i當結尾的長度。

Leetcode 960 : 很多個字串的LIS，不能用Binary_search，因每個字串都不同，算是暴力解吧。