子陣列與子序列問題 (Subarray & Subsequence)#

子陣列和子序列是動態規劃中兩大經典問題類型。理解它們的區別和解題套路，是攻克 DP 面試題的關鍵。

子陣列 vs 子序列#

特性子陣列 (Subarray)子序列 (Subsequence)
連續性必須連續不要求連續
示例[1,2,3] 的子陣列：[1,2], [2,3][1,2,3] 的子序列：[1,3], [1,2,3]
複雜度相對簡單更複雜（組合數為指數級）
備忘錄通常一維或二維通常二維

關鍵區別

  • 子陣列：連續的，答案也必須連續
  • 子序列：可以不連續，但要保持相對順序

例如 "abcde" 中，"ace" 是子序列，但不是子陣列。

子陣列問題#

問題特徵#

  1. 輸入是陣列或字串
  2. 答案是連續的子陣列，或來源於子陣列
  3. 符合 DP 典型特徵（求最優解、可行性、方案數）

經典問題：回文子串個數 ↗#

問題：計算字串中有多少個回文子串。

輸入："aaa"
輸出：6
解釋："a", "a", "a", "aa", "aa", "aaa"
（不同位置的相同字元視為不同子串）

狀態定義：DP[i][j] 表示子串 s[i...j] 是否為回文（True/False）

狀態轉移方程：

$$ DP(i,j) = \begin{cases} DP[i+1][j-1], & s[i] = s[j] \ False, & s[i] \neq s[j] \end{cases} $$

最佳化技巧：當 s[i] == s[j] 且 j - i < 3 時，必定是回文。

回文子串
fun countSubstrings(s: String): Int {
    val n = s.length
    if (n == 0) return 0

    var ans = 0
    val dp = Array(n) { BooleanArray(n) }

    // 初始化：單個字元是回文
    for (i in 0 until n) {
        dp[i][i] = true
        ans++
    }

    // 填充 DP 表
    for (j in 1 until n) {
        for (i in 0 until j) {
            // 優化：長度 < 3 且首尾相等必定回文
            dp[i][j] = s[i] == s[j] && (j - i < 3 || dp[i + 1][j - 1])
            if (dp[i][j]) ans++
        }
    }

    return ans
}

經典問題：最大子陣列之和 ↗#

問題：找到具有最大和的連續子陣列。

輸入：[-2, 1, -3, 4, -1, 3, -5, 1, 2]
輸出：6
解釋：連續子陣列 [4, -1, 3] 的和最大

備忘錄定義的陷阱 如果將 DP[i] 定義為「nums[0...i] 中的最大子陣列之和」，會導致無法正確推導。 因為子陣列必須連續，但 DP[i-1] 的最優解不一定與 nums[i] 相連。

正確的狀態定義：DP[i] 表示以 i 為結束位置的最大子陣列之和

狀態轉移方程：

$$ DP(i) = \begin{cases} 0, & i = 0 \ \max(nums[i], nums[i] + DP[i-1]), & i > 0 \end{cases} $$

決策邏輯：

  • 開始新子陣列：nums[i]
  • 延續舊子陣列：nums[i] + DP[i-1]
最大子陣列之和
fun maxSubArray(nums: IntArray): Int {
    val n = nums.size
    if (n == 0) return 0

    val dp = IntArray(n)
    dp[0] = nums[0]
    var res = dp[0]

    for (i in 1 until n) {
        // 決策：開始新的 vs 延續舊的
        dp[i] = maxOf(nums[i], dp[i - 1] + nums[i])
        res = maxOf(res, dp[i])
    }

    return res
}

空間最佳化：由於 DP[i] 只依賴 DP[i-1]，可以壓縮到 O(1)。

fun maxSubArray(nums: IntArray): Int {
    var dpPrev = nums[0]
    var res = nums[0]
    for (i in 1 until nums.size) {
        val dpCurr = maxOf(nums[i], dpPrev + nums[i])
        dpPrev = dpCurr
        res = maxOf(res, dpCurr)
    }
    return res
}

逆向思維看 Kadane#

最大子陣列和的線性解，核心是上面那條「以每個位置結尾的最大子陣列」遞推。但為什麼這樣就能保證 O(n)？除了「狀態只依賴前一格」這個機械式的解釋外，還有一個更直觀的視角能說明它為何成立。

把問題拆成兩半來想：

  • 若已知最大子陣列的左端點：那右端點是哪一個就不用猜了——從左端點往右累加，只要往右掃一遍，記錄掃過的累積和的最大值出現在哪，就定出了右端點。
  • 若已知右端點：對稱地，把序列倒過來掃，同樣一遍就能定出左端點。

換句話說，只要固定住區間的一端，另一端就能用單次線性掃描定出來。Kadane 之所以是 O(n)，本質正是把「枚舉左端點 × 枚舉右端點」這個 O(n²) 的雙重迴圈，化簡成「每個位置只當一次右端點、左端點隨之被遞推確定」的單層掃描。dp[i] = max(nums[i], dp[i-1] + nums[i]) 裡的那個 max，做的就是「要不要把左端點重新拉到 i」這個決策。

正反兩遍掃描 / 逆向思維 「固定一端、線性掃出另一端；正著掃不行就把序列倒過來掃」是處理區間類問題的通用技巧。當一個問題正面枚舉是平方級，不妨問自己：能不能假設答案的一端已知，再用一遍掃描補出另一端？更完整的討論見演算法思維總綱。

和等於 k 的子陣列 ↗#

問題：給定一個整數陣列（可能含負數），求有幾個「連續子陣列」的和恰好等於 k。

輸入：nums = [1, 2, 3], k = 3
輸出：2
解釋：[1, 2] 和 [3] 兩個連續子陣列的和都是 3

為什麼不能用滑動視窗？ 滑動視窗依賴「擴張視窗 ➡️ 和變大、收縮視窗 ➡️ 和變小」這個單調性。一旦陣列含負數，加入元素也可能讓和變小，單調性就被破壞，滑動視窗不再適用。

核心思路：前綴和 + 雜湊表

令 prefix[t] 為 nums[0..t-1] 的前綴和。那麼子陣列 (i, j]（即 nums[i+1..j]）的和就是 prefix[j] - prefix[i]。要它等於 k：

$$ prefix[j] - prefix[i] = k ;\Longleftrightarrow; prefix[i] = prefix[j] - k $$

於是問題轉化成：掃到位置 j 時，前面出現過幾個前綴和等於 prefix[j] - k，就有幾個以 j 結尾、和為 k 的子陣列。用一個雜湊表邊掃邊記錄「每個前綴和出現過幾次」，一遍掃完即可，時間 O(n)。

初始化 {0: 1} 的意義 雜湊表要先放入 {0: 1}，代表「一個元素都還沒加入時，前綴和為 0 出現過一次」。這樣才能涵蓋「從陣列開頭一路算到 j、整段和就等於 k」的情況（此時 prefix[j] - k = 0）。漏了它就會少算這類答案。

和等於 k 的子陣列
fun subarraySum(nums: IntArray, k: Int): Int {
    // key: 前綴和；value: 該前綴和出現的次數
    val count = HashMap<Int, Int>()
    count[0] = 1  // 空前綴：和為 0 出現一次

    var prefix = 0
    var res = 0
    for (num in nums) {
        prefix += num
        // 找有幾個更早的前綴和等於 prefix - k
        res += count.getOrDefault(prefix - k, 0)
        // 把當前前綴和記錄下來（等同 Python defaultdict 的自動補 0）
        count[prefix] = count.getOrDefault(prefix, 0) + 1
    }
    return res
}

這跟「兩數之和」是同一招 兩數之和是「掃到 num 時，找前面有沒有出現過補數 target - num」；這裡是「掃到 prefix 時，找前面有沒有出現過 prefix - k」。兩者都是用雜湊表把「往前找配對」從 O(n) 查找壓成 O(1)，整體降到 O(n)。延伸閱讀：前綴和與雜湊應用。

子序列問題#

問題特徵#

  1. 涉及「子序列」關鍵詞
  2. 符合 DP 典型特徵，特別是求「最」優解
  3. 暴力解法是指數級別，幾乎必須用 DP

經驗法則 一旦問題涉及子序列，幾乎不需要考慮 DP 以外的解法。 子序列的組合數是指數級的，只有 DP 能將其降到多項式級別。

經典問題：最長回文子序列 ↗#

問題：找到字串中最長的回文子序列的長度。

輸入："asssasms"
輸出：5
解釋：最長回文子序列是 "sssss" 或 "asssa"

狀態定義：DP[i][j] 表示字串 s[i...j] 中最長回文子序列的長度

狀態轉移方程：

$$ DP(i,j) = \begin{cases} 2 + DP[i+1][j-1], & s[i] = s[j] \ \max(DP[i+1][j], DP[i][j-1]), & s[i] \neq s[j] \end{cases} $$

計算方向：這裡需要特別注意！

最終答案在 DP[0][n-1]
當前狀態依賴：DP[i+1][j-1]、DP[i+1][j]、DP[i][j-1]
計算方向：從右下角往左上角（i 從大到小，j 從小到大）
最長回文子序列
fun longestPalindromeSubseq(s: String): Int {
    val n = s.length
    if (n == 0) return 0

    val dp = Array(n) { IntArray(n) }

    // 初始化：單個字元的回文長度為 1
    for (i in 0 until n) dp[i][i] = 1

    // 注意計算方向：i 從大到小
    for (i in n - 1 downTo 0) {
        for (j in i + 1 until n) {
            if (s[i] == s[j]) {
                dp[i][j] = 2 + dp[i + 1][j - 1]
            } else {
                dp[i][j] = maxOf(dp[i + 1][j], dp[i][j - 1])
            }
        }
    }

    return dp[0][n - 1]
}

經典問題：最長遞增子序列 (LIS)#

問題：找到陣列中最長嚴格遞增子序列 ↗的長度。

輸入：[10, 9, 2, 5, 3, 7, 101, 18]
輸出：4
解釋：最長遞增子序列是 [2, 3, 7, 101] 或 [2, 5, 7, 101]

關鍵區別

  • 子序列：不需要連續，只需保持相對順序
  • 子陣列：必須連續

若題目允許調換順序，問題就退化成排序了。

動態規劃解法（O(N²)）#

狀態定義：dp[i] 表示以 nums[i] 結尾的最長遞增子序列長度

狀態轉移方程： $$dp[i] = \max_{0 \le j < i, nums[j] < nums[i]}(dp[j] + 1)$$

最終答案是 max(dp[0..n-1])，而不是 dp[n-1]。 因為最長子序列不一定以最後一個元素結尾。

動態規劃實作
fun lengthOfLIS(nums: IntArray): Int {
    if (nums.isEmpty()) return 0

    val dp = IntArray(nums.size) { 1 }  // 每個元素本身就是長度 1 的子序列
    var result = 1

    for (i in 1 until nums.size) {
        for (j in 0 until i) {
            if (nums[j] < nums[i]) {
                dp[i] = maxOf(dp[i], dp[j] + 1)
            }
        }
        result = maxOf(result, dp[i])
    }

    return result
}

貪心 + 二分搜尋（O(N log N)）#

核心思想：維護一個遞增陣列 tails，其中 tails[i] 表示長度為 i+1 的遞增子序列的最小結尾元素。

操作規則：

  • 若 num > tails 末尾：直接追加
  • 否則：用二分搜尋找到第一個 >= num 的位置，替換它

為什麼要替換？ 子序列結尾越小，後面能接上的元素就越多。這是貪心策略的體現。

貪心 + 二分實作
fun lengthOfLIS(nums: IntArray): Int {
    val tails = IntArray(nums.size)
    var size = 0

    for (num in nums) {
        // 二分搜尋：找第一個 >= num 的位置
        var lo = 0
        var hi = size
        while (lo < hi) {
            val mid = lo + (hi - lo) / 2  // 避免整數溢位
            if (tails[mid] < num) {
                lo = mid + 1
            } else {
                hi = mid
            }
        }

        tails[lo] = num
        if (lo == size) size++
    }

    return size
}

tails 陣列的內容不是真正的 LIS（順序可能被打亂），但其長度是正確答案。 若需要輸出具體序列，需額外記錄路徑。

經典問題：最長公共子序列 (LCS ↗)#

問題：給定兩個字串，返回最長公共子序列的長度。

輸入：text1 = "abcde", text2 = "ace"
輸出：3
解釋：最長公共子序列是 "ace"

狀態定義：DP[i][j] 表示 text1[0...i] 和 text2[0...j] 的 LCS 長度

狀態轉移方程：

$$ DP(i,j) = \begin{cases} 1 + DP[i-1][j-1], & text1[i-1] = text2[j-1] \ \max(DP[i-1][j], DP[i][j-1]), & text1[i-1] \neq text2[j-1] \end{cases} $$

初始化技巧 設置一個空字元作為計算起點：

  • DP[0][j] = 0（空字串與任何字串的 LCS 為 0）
  • DP[i][0] = 0

這樣真正的字串迭代就有了初始值。

最長公共子序列
fun longestCommonSubsequence(text1: String, text2: String): Int {
    val m = text1.length
    val n = text2.length
    val dp = Array(m + 1) { IntArray(n + 1) }

    // 初始化（多一行一列為空字串）
    // dp[0][...] 和 dp[...][0] 預設為 0

    for (i in 1..m) {
        for (j in 1..n) {
            if (text1[i - 1] == text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1
            } else {
                dp[i][j] = maxOf(dp[i - 1][j], dp[i][j - 1])
            }
        }
    }

    return dp[m][n]
}

計算方向詳解#

計算方向是 DP 中的關鍵概念，決定了填充備忘錄的順序。

確定計算方向的方法#

  1. 找出依賴關係：當前狀態依賴哪些更小的子問題
  2. 確定結果位置：最終答案存放在哪裡
  3. 從已知推向未知：確保計算時依賴的狀態已計算完成

示例對比#

問題依賴關係結果位置計算方向
最大子陣列和DP[i-1]max(DP[0...n])從左到右
最長回文子序列DP[i+1][j-1], DP[i+1][j], DP[i][j-1]DP[0][n-1]從右下到左上
LCSDP[i-1][j-1], DP[i-1][j], DP[i][j-1]DP[m][n]從左上到右下

備忘錄定義總結#

核心原則 備忘錄的定義必須能夠建立起「當前狀態」與「子問題」之間的關係。 錯誤的定義會導致無法寫出狀態轉移方程。

子陣列問題#

  • 通常定義為「以 i 結尾」的形式
  • 保證連續性的要求

子序列問題#

  • 單字串：DP[i][j] 表示區間 [i, j] 的解
  • 雙字串：DP[i][j] 表示前綴 [0, i] 和 [0, j] 的解

狀態壓縮原則#

若 DP[i] 只依賴 DP[i-1] → 可壓縮到兩個變數
若 DP[i][j] 只依賴當前行和上一行 → 可壓縮到兩行
Backward 背包問題 經典DP問題 Forward