两道必掌握的动态规划面试题：最长回文子串 最长公共子序列

目录一、最长回文子串Longest Palindromic Substring题目描述1. 暴力解法时间复杂度 O (n³)2. 中心扩展法时间复杂度 O (n²)空间 O (1)核心思路Java 代码实现3. 动态规划解法时间复杂度 O (n²)空间 O (n²)DP 定义状态转移方程Java 代码实现二、最长公共子序列Longest Common Subsequence, LCS题目描述1. 动态规划解法时间复杂度 O (mn)空间 O (mn)DP 定义状态转移方程Java 代码实现2. 空间优化时间复杂度 O (mn)空间 O (min (m,n))三、面试核心考点对比四、写在最后在算法面试中动态规划DP是当之无愧的高频考点。其中最长回文子串和最长公共子序列更是出现频率极高的两道经典题目。它们不仅是理解动态规划思想的绝佳案例也常常作为更复杂 DP 问题的基础模块。今天我们就来把这两道题彻底吃透。一、最长回文子串Longest Palindromic Substring题目描述给定一个字符串s找到s中最长的回文子串。回文串正读和反读都相同的字符串。示例输入babad→ 输出bab或aba输入cbbd→ 输出bb1. 暴力解法时间复杂度 O (n³)最容易想到的思路是枚举所有子串判断是否为回文串记录最长的那个。子串数量O (n²)判断回文O (n)总复杂度O (n³)字符串稍长就会超时不推荐。2. 中心扩展法时间复杂度 O (n²)空间 O (1)回文串有一个核心特征它可以由一个中心向两边扩展得到。奇数长度中心是一个字符如aba中心是b偶数长度中心是两个字符之间如abba中心在两个b之间核心思路遍历每个可能的中心向左右扩展直到不再满足回文条件记录过程中最长的回文子串。Java 代码实现java运行public String longestPalindrome(String s) { if (s null || s.length() 1) return ; int start 0, end 0; for (int i 0; i s.length(); i) { // 奇数长度 int len1 expandAroundCenter(s, i, i); // 偶数长度 int len2 expandAroundCenter(s, i, i 1); int len Math.max(len1, len2); if (len end - start) { start i - (len - 1) / 2; end i len / 2; } } return s.substring(start, end 1); } private int expandAroundCenter(String s, int left, int right) { while (left 0 right s.length() s.charAt(left) s.charAt(right)) { left--; right; } // 返回回文串长度 return right - left - 1; }3. 动态规划解法时间复杂度 O (n²)空间 O (n²)DP 定义定义dp[i][j]表示s[i..j]是否为回文子串。状态转移方程当i j时单个字符dp[i][j] true当j i 1时两个字符dp[i][j] (s[i] s[j])当j i 1时dp[i][j] (s[i] s[j] dp[i1][j-1])Java 代码实现java运行public String longestPalindrome(String s) { int n s.length(); if (n 2) return s; boolean[][] dp new boolean[n][n]; int maxLen 1, start 0; // 单个字符都是回文 for (int i 0; i n; i) dp[i][i] true; // 枚举子串长度 for (int len 2; len n; len) { for (int i 0; i n - len; i) { int j i len - 1; if (s.charAt(i) ! s.charAt(j)) { dp[i][j] false; } else { if (j - i 3) { dp[i][j] true; } else { dp[i][j] dp[i1][j-1]; } } if (dp[i][j] len maxLen) { maxLen len; start i; } } } return s.substring(start, start maxLen); }二、最长公共子序列Longest Common Subsequence, LCS题目描述给定两个字符串text1和text2返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列返回 0。子序列不要求连续但相对顺序必须保持一致。示例输入text1 abcde, text2 ace→ 输出3ace输入text1 abc, text2 def→ 输出01. 动态规划解法时间复杂度 O (mn)空间 O (mn)这是一道非常经典的二维 DP 问题也是很多字符串 DP 问题的模板。DP 定义定义dp[i][j]表示text1[0..i-1]和text2[0..j-1]的最长公共子序列长度。用i-1和j-1是为了方便处理边界情况状态转移方程如果text1[i-1] text2[j-1]dp[i][j] dp[i-1][j-1] 1如果text1[i-1] ! text2[j-1]dp[i][j] Math.max(dp[i-1][j], dp[i][j-1])Java 代码实现java运行public int longestCommonSubsequence(String text1, String text2) { int m text1.length(), n text2.length(); int[][] dp new int[m 1][n 1]; 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]; }2. 空间优化时间复杂度 O (mn)空间 O (min (m,n))因为每次计算dp[i][j]只需要上一行和当前行的值我们可以用一维数组来优化空间。java运行public int longestCommonSubsequence(String text1, String text2) { // 保证 text2 是较短的字符串 if (text1.length() text2.length()) { return longestCommonSubsequence(text2, text1); } int m text1.length(), n text2.length(); int[] dp new int[n 1]; for (int i 1; i m; i) { int prev 0; // 保存 dp[i-1][j-1] for (int j 1; j n; j) { int temp dp[j]; if (text1.charAt(i - 1) text2.charAt(j - 1)) { dp[j] prev 1; } else { dp[j] Math.max(dp[j], dp[j - 1]); } prev temp; } } return dp[n]; }三、面试核心考点对比表格题目核心思想推荐解法关键区别最长回文子串利用回文串的对称性中心扩展法处理 “连续” 的子串关注对称性最长公共子序列利用 DP 记录子问题二维动态规划处理 “非连续” 的子序列关注公共性四、写在最后这两道题是算法面试的 “敲门砖”掌握它们不仅是为了应付面试更是为了建立起动态规划的解题思维。遇到字符串问题先想想能不能用 DP 建模遇到回文问题优先考虑中心扩展法遇到两个字符串的比较问题优先考虑二维 DP。