序列问题 (Sequence DP)

核心思想

处理字符串/数组的子序列、字串问题，通常用 dp[i][j] 表示以 s1[i] 和 s2[j] 结尾的状态。

1. 最长公共子序列 (LCS)

问题

两个字符串 s1, s2 的最长公共子序列长度

解法

typescript

function longestCommonSubsequence(s1: string, s2: string): number {
  const m = s1.length, n = s2.length;
  // dp[i][j] = s1[0..i-1] 与 s2[0..j-1] 的 LCS 长度
  const dp: number[][] = Array.from({ length: m + 1 }, () =>
    Array(n + 1).fill(0)
  );

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s1[i - 1] === s2[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];
}

// ✅ 空间优化
function lcsOptimized(s1: string, s2: string): number {
  const n = s2.length;
  let dp = Array(n + 1).fill(0);

  for (let i = 1; i <= s1.length; i++) {
    let prev = 0; // dp[i-1][j-1]
    for (let j = 1; j <= n; j++) {
      const temp = dp[j];
      if (s1[i - 1] === s2[j - 1]) {
        dp[j] = prev + 1;
      } else {
        dp[j] = Math.max(dp[j], dp[j - 1]);
      }
      prev = temp;
    }
  }

  return dp[n];
}

状态转移

2. 最长递增子序列 (LIS)

问题

数组的最长严格递增子序列长度

解法 - O(n²)

typescript

function lengthOfLIS(nums: number[]): number {
  const n = nums.length;
  // dp[i] = 以 nums[i] 结尾的 LIS 长度
  const dp = Array(n).fill(1);

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

  return Math.max(...dp);
}

解法 - O(n log n) 二分优化

typescript

function lengthOfLISBinary(nums: number[]): number {
  const tails: number[] = [];

  for (const num of nums) {
    // 找到第一个 >= num 的位置
    let left = 0, right = tails.length;
    while (left < right) {
      const mid = (left + right) >> 1;
      if (tails[mid] < num) left = mid + 1;
      else right = mid;
    }

    if (left === tails.length) {
      tails.push(num);
    } else {
      tails[left] = num;
    }
  }

  return tails.length;
}

二分优化原理

tails[i] = 长度为 i+1 的递增子序列的最小结尾值
维护一个有序数组，用二分查找

3. 编辑距离

问题

将 word1 转为 word2 的最少操作数（插入、删除、替换）

解法

typescript

function minDistance(word1: string, word2: string): number {
  const m = word1.length, n = word2.length;
  // dp[i][j] = word1[0..i-1] 转为 word2[0..j-1] 的最小代价
  const dp: number[][] = Array.from({ length: m + 1 }, (_, i) =>
    Array(n + 1).fill(0).map((_, j) => (i === 0 ? j : j === 0 ? i : 0))
  );

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = Math.min(
          dp[i - 1][j] + 1,     // 删除
          dp[i][j - 1] + 1,     // 插入
          dp[i - 1][j - 1] + 1  // 替换
        );
      }
    }
  }

  return dp[m][n];
}

状态转移

操作	dp[i][j]
相等	`dp[i-1][j-1]`
删除	`dp[i-1][j] + 1`
插入	`dp[i][j-1] + 1`
替换	`dp[i-1][j-1] + 1`

4. 最长公共子串

与 LCS 的区别

问题	子串 vs 子序列
子串	必须连续
子序列	可以不连续

typescript

function longestCommonSubstring(s1: string, s2: string): number {
  const m = s1.length, n = s2.length;
  let maxLen = 0;

  // dp[i][j] = 以 s1[i-1], s2[j-1] 结尾的公共子串长度
  const dp: number[][] = Array.from({ length: m + 1 }, () =>
    Array(n + 1).fill(0)
  );

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s1[i - 1] === s2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
        maxLen = Math.max(maxLen, dp[i][j]);
      } else {
        dp[i][j] = 0; // 必须连续，不连续则断开
      }
    }
  }

  return maxLen;
}

5. 重复子序列问题

最长重复子串

typescript

function longestRepeatedSubstring(s: string): string {
  const n = s.length;
  // dp[i][j] = s[i..j] 的最长重复子串长度
  const dp: number[][] = Array.from({ length: n }, () => Array(n).fill(0));
  let maxLen = 0;
  let endIndex = 0;

  for (let i = n - 2; i >= 0; i--) {
    for (let j = i + 1; j < n; j++) {
      if (s[i] === s[j]) {
        dp[i][j] = dp[i + 1][j - 1] + 1;
        if (dp[i][j] > maxLen) {
          maxLen = dp[i][j];
          endIndex = j;
        }
      }
    }
  }

  return s.substring(endIndex - maxLen + 1, endIndex + 1);
}

6. 最长回文子串

问题

找出字符串中最长的回文子串（必须连续）

解法对比

typescript

// 方法1: 中心扩展 O(n²)
function longestPalindrome(s: string): string {
  let longest = "";

  const expand = (left: number, right: number): void => {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      if (right - left + 1 > longest.length) {
        longest = s.substring(left, right + 1);
      }
      left--;
      right++;
    }
  };

  for (let i = 0; i < s.length; i++) {
    expand(i, i);       // 奇数长度 (aba)
    expand(i, i + 1);   // 偶数长度 (aa)
  }

  return longest;
}

// 方法2: 动态规划 O(n²)
function longestPalindromeDP(s: string): string {
  const n = s.length;
  // dp[i][j] = s[i..j] 是否为回文串
  const dp: boolean[][] = Array.from({ length: n }, () => Array(n).fill(false));

  let start = 0, maxLen = 1;

  // 初始化: 单字符都是回文
  for (let i = 0; i < n; i++) {
    dp[i][i] = true;
  }

  // 按长度递增
  for (let len = 2; len <= n; len++) {
    for (let i = 0; i + len <= n; i++) {
      const j = i + len - 1;

      if (len === 2) {
        dp[i][j] = s[i] === s[j];
      } else {
        dp[i][j] = s[i] === s[j] && dp[i + 1][j - 1];
      }

      if (dp[i][j] && len > maxLen) {
        start = i;
        maxLen = len;
      }
    }
  }

  return s.substring(start, start + maxLen);
}

// 方法3: Manacher 算法 O(n) - 最优
function longestPalindromeManacher(s: string): string {
  // 预处理: 用特殊字符分隔
  const t = "^#" + s.split("").join("#") + "#$";
  const n = t.length;
  const P = Array(n).fill(0);
  let center = 0, right = 0;

  for (let i = 1; i < n - 1; i++) {
    if (i < right) {
      P[i] = Math.min(right - i, P[2 * center - i]);
    }

    while (t[i + P[i] + 1] === t[i - P[i] - 1]) {
      P[i]++;
    }

    if (i + P[i] > right) {
      center = i;
      right = i + P[i];
    }
  }

  // 找最长
  let maxLen = 0, idx = 0;
  for (let i = 1; i < n - 1; i++) {
    if (P[i] > maxLen) {
      maxLen = P[i];
      idx = i;
    }
  }

  const start = (idx - maxLen) / 2;
  return s.substring(start, start + maxLen);
}

三种方法对比

方法	时间	空间	适用场景
中心扩展	O(n²)	O(1)	面试/简单实现
动态规划	O(n²)	O(n²)	需多次查询
Manacher	O(n)	O(n)	追求最优

DP 状态转移图解

s = "babad"

状态: dp[i][j] = s[i..j] 是否回文

初始化: dp[i][i] = true

长度=1: "b", "a", "b", "a", "d"  → 全为 true
长度=2: "ba"(false), "ab"(false), "ba"(false), "ad"(false)
长度=3: "bab"(true) ← s[0]==s[2] && dp[1][1]
        "aba"(true) ← s[1]==s[3] && dp[2][2]
长度=4: "baba"(false), "abad"(false)
长度=5: "babad"(false)

最长: "bab" 或 "aba"

7. 回文子序列 vs 回文子串

关键区别

特征	回文子串	回文子序列
是否连续	✅ 必须连续	❌ 可不连续
示例	`"aba"` 是 `"aabb"` 的回文子串	`"aba"` 是 `"aabb"` 的回文子序列
数量	O(n²)	可能 O(2^n)

最长回文子序列

typescript

function longestPalindromeSubseq(s: string): number {
  const n = s.length;
  // dp[i][j] = s[i..j] 的最长回文子序列长度
  const dp: number[][] = Array.from({ length: n }, () => Array(n).fill(0));

  // 初始化: 单字符
  for (let i = 0; i < n; i++) {
    dp[i][i] = 1;
  }

  // 按长度递增 (从短到长)
  for (let len = 2; len <= n; len++) {
    for (let i = 0; i + len <= n; i++) {
      const j = i + len - 1;

      if (s[i] === s[j]) {
        dp[i][j] = dp[i + 1][j - 1] + 2;
      } else {
        dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
      }
    }
  }

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

对比图解

s = "bbbab"

回文子串（连续）: "bbb", "bb", "b", "bab" → 最长 "bbb"
回文子序列（可不连续）: "bbbb", "bbb", "bb", "b" → 最长 "bbbb"

8. 序列 DP 统一模板

模板速查表

问题	DP 维度	状态定义	转移
LCS	2D	`dp[i][j]` = 前i/j的最优	相等→斜角，不等→max
LIS	1D	`dp[i]` = 以i结尾	枚举j找更小
编辑距离	2D	`dp[i][j]` = 转换代价	min(删除,插入,替换)
回文子串	2D	`dp[i][j]` = 是否回文	收缩边界
回文子序列	2D	`dp[i][j]` = 最长长度	相等→+2，不等→max

通用代码框架

typescript

// 二维序列 DP 标准模板
function sequenceDP(s1: string, s2: string): number {
  const m = s1.length, n = s2.length;
  const dp: number[][] = Array.from({ length: m + 1 }, () =>
    Array(n + 1).fill(0)
  );

  // 初始化
  for (let i = 0; i <= m; i++) dp[i][0] = 0;
  for (let j = 0; j <= n; j++) dp[0][j] = 0;

  // 填表
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s1[i - 1] === s2[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];
}

空间优化技巧

typescript

// 二维 → 一维
function optimizeSequenceDP(s1: string, s2: string): number {
  const n = s2.length;
  let dp = Array(n + 1).fill(0);

  for (let i = 1; i <= s1.length; i++) {
    let prev = 0; // 保存 dp[i-1][j-1]
    for (let j = 1; j <= n; j++) {
      const temp = dp[j];
      if (s1[i - 1] === s2[j - 1]) {
        dp[j] = prev + 1;
      } else {
        dp[j] = Math.max(dp[j], dp[j - 1]);
      }
      prev = temp;
    }
  }

  return dp[n];
}

9. 字符串匹配类问题

正则表达式匹配

typescript

function isMatch(s: string, p: string): boolean {
  const m = s.length, n = p.length;
  // dp[i][j] = s[0..i-1] 是否匹配 p[0..j-1]
  const dp: boolean[][] = Array.from({ length: m + 1 }, () =>
    Array(n + 1).fill(false)
  );

  dp[0][0] = true;

  // 初始化: s为空，p能否匹配空字符串
  for (let j = 1; j <= n; j++) {
    if (p[j - 1] === '*') {
      dp[0][j] = dp[0][j - 2]; // x* 可以匹配零个字符
    }
  }

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (p[j - 1] === '*') {
        // 不匹配 x* 或 匹配一个 x*
        dp[i][j] = dp[i][j - 2] ||
                   (p[j - 2] === '.' || p[j - 2] === s[i - 1]) && dp[i - 1][j];
      } else if (p[j - 1] === '.' || p[j - 1] === s[i - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      }
    }
  }

  return dp[m][n];
}

通配符匹配

typescript

function isWildcardMatch(s: string, p: string): boolean {
  const m = s.length, n = p.length;
  const dp: boolean[][] = Array.from({ length: m + 1 }, () =>
    Array(n + 1).fill(false)
  );

  dp[0][0] = true;

  // 处理 * 开头的匹配空字符串
  for (let j = 1; j <= n; j++) {
    if (p[j - 1] === '*') {
      dp[0][j] = dp[0][j - 1];
    }
  }

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (p[j - 1] === '*') {
        // * 匹配0个 或 * 匹配1个
        dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
      } else if (p[j - 1] === '?' || p[j - 1] === s[i - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      }
    }
  }

  return dp[m][n];
}

参见: **DP算法索引** | **路径问题**

序列问题 (Sequence DP) ​

1. 最长公共子序列 (LCS) ​

问题 ​

解法 ​

状态转移 ​

2. 最长递增子序列 (LIS) ​

问题 ​

解法 - O(n²) ​

解法 - O(n log n) 二分优化 ​

3. 编辑距离 ​

问题 ​

解法 ​

状态转移 ​

4. 最长公共子串 ​

与 LCS 的区别 ​

5. 重复子序列问题 ​

最长重复子串 ​

6. 最长回文子串 ​

问题 ​

解法对比 ​

三种方法对比 ​

DP 状态转移图解 ​

7. 回文子序列 vs 回文子串 ​

关键区别 ​

最长回文子序列 ​

对比图解 ​

8. 序列 DP 统一模板 ​

模板速查表 ​

通用代码框架 ​

空间优化技巧 ​

9. 字符串匹配类问题 ​

正则表达式匹配 ​

通配符匹配 ​

序列问题 (Sequence DP)

1. 最长公共子序列 (LCS)

问题

解法

状态转移

2. 最长递增子序列 (LIS)

问题

解法 - O(n²)

解法 - O(n log n) 二分优化

3. 编辑距离

问题

解法

状态转移

4. 最长公共子串

与 LCS 的区别

5. 重复子序列问题

最长重复子串

6. 最长回文子串

问题

解法对比

三种方法对比

DP 状态转移图解

7. 回文子序列 vs 回文子串

关键区别

最长回文子序列

对比图解

8. 序列 DP 统一模板

模板速查表

通用代码框架

空间优化技巧

9. 字符串匹配类问题

正则表达式匹配

通配符匹配