子序列的問題通常都比子字串或是子陣列問題更加困難，因為子序列沒有要求要連續，而其餘兩者都要求要連續．有的時候連列舉一個暴力解都非常困難，更別說要得到演算法了

此外，子序列問題有可能會涉及二個字串的處理，如同昨天的最長公用次序列．需要一定的經驗，才能夠不踩坑解出來．

一般來說，這類題目都是求一個最長子序列(最短就只有一個字元就可以了)，所以看到子序列與極值的問題，基本上都是考驗動態規劃，而時間複雜度通常都是O(n^2)

既然使用動態規劃，就要定義dp陣列，來尋找狀態轉移的關係．通常會使用以下兩種思路

一維dp陣列

    val n = inputArray.size

    val dp :Array<Int> = Array(n){0}

    for(i in 1 until n){
        for(j in 0 until i){
            dp[i] = 極值(dp[i], dp[j]+...)
        }
    }

以昨天的最長遞增子序列為例子，如果以這個思路套入，那dp矩陣的定義就是

在子陣列array[0..i]中，以array[i]為結尾的最長遞增子序列，其長度為dp[i]

這樣定義的原因就是比較容易使用歸納法，找到狀態轉移的關係

二維dp陣列

		val n = inputArray.size
    val dp: Array<Array<Int>> = Array(n) { Array(n) { 0 } }
    for (i in 1 until n) {
        for (j in 0 until n) {//這邊不同了
            if(inputArray[i] == inputArray[j]){
                dp[i][j] = dp[i][j] + ...
            }else{
                dp[i][j] = 極值(...)
            }
        }
    }

這種作法的運用場景比較多，尤其是兩個字串/陣列的子序列都常常用到．例如前面兩題最長公用次序列跟字串編輯距離都有用到

而dp陣列的含義，又分成”只涉及到一個字串”和”同時涉及到兩個字串”兩種

• 涉及兩個字串/陣列 (如最長公用次序列)，含義如下
  在子陣列

在子陣列arr1[0..i]跟子陣列arr2[0..j]，要求的子序列(最長公用次序列)長度為dp[i][j]

• 只涉及一個字串/陣列，含義如下:

在子陣列arr[i..j]中，要求的子序列的長度為dp[i][j]

這個方向我們還沒解過，我們明天會使用一個最長回文子序列問題來熟悉