子陣列與子序列問題#

子陣列和子序列是動態規劃中兩大經典問題類型。理解它們的區別和解題套路，是攻克 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 時，必定是回文。

回文子串 Java 實現
int countSubstrings(String s) {
    int n = s.length();
    if (n == 0) return 0;

    int ans = 0;
    boolean[][] dp = new boolean[n][n];

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

    // 填充 DP 表
    for (int j = 1; j < n; j++) {
        for (int i = 0; i < j; i++) {
            // 優化：長度 < 3 且首尾相等必定回文
            dp[i][j] = (s.charAt(i) == s.charAt(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]
最大子陣列之和 Java 實現
int maxSubArray(int[] nums) {
    int n = nums.length;
    if (n == 0) return 0;

    int[] dp = new int[n];
    dp[0] = nums[0];
    int res = dp[0];

    for (int i = 1; i < n; i++) {
        // 決策：開始新的 vs 延續舊的
        dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
        res = Math.max(res, dp[i]);
    }

    return res;
}

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

int maxSubArray(int[] nums) {
    int dp_prev = nums[0], res = dp_prev;
    for (int i = 1; i < nums.length; i++) {
        int dp_curr = Math.max(nums[i], dp_prev + nums[i]);
        dp_prev = dp_curr;
        res = Math.max(res, dp_curr);
    }
    return res;
}

子序列問題#

問題特徵#

  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 從小到大）
最長回文子序列 Java 實現
int getLongestPalindromeSubseq(String s) {
    int n = s.length();
    if (n == 0) return 0;

    int[][] dp = new int[n][n];

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

    // 注意計算方向：i 從大到小
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i + 1; j < n; j++) {
            if (s.charAt(i) == s.charAt(j)) {
                dp[i][j] = 2 + dp[i + 1][j - 1];
            } else {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[0][n - 1];
}

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

問題：找到陣列中最長嚴格遞增子序列的長度。（LeetCode 300）

輸入：[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]。 因為最長子序列不一定以最後一個元素結尾。

動態規劃實現
int lengthOfLIS(int[] nums) {
    if (nums.length == 0) return 0;

    int[] dp = new int[nums.length];
    Arrays.fill(dp, 1);  // 每個元素本身就是長度 1 的子序列
    int result = 1;

    for (int i = 1; i < nums.length; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        result = Math.max(result, dp[i]);
    }

    return result;
}

解法二：貪心 + 二分搜尋 O(N log N)#

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

操作規則：

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

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

貪心 + 二分實現
int lengthOfLIS(int[] nums) {
    int[] tails = new int[nums.length];
    int size = 0;

    for (int num : nums) {
        // 二分搜尋：找第一個 >= num 的位置
        int lo = 0, hi = size;
        while (lo < hi) {
            int mid = (lo + hi) / 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

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

最長公共子序列 Java 實現
int getLongestCommonSubsequence(String text1, String text2) {
    int m = text1.length(), n = text2.length();
    int[][] dp = new int[m + 1][n + 1];

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

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(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