手撕代码必备！3道字符串动态规划难题一网打尽
🔑 为什么动态规划是字符串处理的必修课？
在技术面试中，90%的字符串难题都暗藏动态规划杀机。本文将以最长回文子串（LeetCode 5）、最长公共子序列（LeetCode 1143）和编辑距离（LeetCode 72）三大经典案例，带你破解字符串DP的核心套路。
–
一、最长回文子串：二维DP的经典演绎
1.1 问题本质
给定字符串s，找到其最长回文子串。注意：回文串要求连续字符对称排列。
1.2 动态规划解法
func longestPalindrome(s string) string {
n := len(s)
dp := make([][]bool, n)
start, maxLen := 0, 1
// 初始化及状态转移逻辑
// ...
return s[start:start+maxLen]
}核心逻辑：
✅ dp[i][j]表示s[i..j]是否为回文
✅ 边界条件：单个字符或相邻相同字符
✅ 状态转移：s[i]==s[j] && dp[i+1][j到1]==true
–
二、最长公共子序列：跨字符串匹配的终极方案
2.1 问题特点
给定两个字符串text1和text2，返回它们的最长公共子序列长度。注意：子序列不要求连续。
2.2 DP状态转移
| 字符匹配 | 转移方程 |
|---|---|
| text1[i] == text2[j] | dp[i][j] = dp[i到1][j-1] + 1 |
| text1[i] != text2[j] | dp[i][j] = max(dp[i到1][j], dp[i][j-1]) |
–
三、编辑距离：字符串变换的成本核算
3.1 操作成本模型
三种操作成本均为1：
🔹 插入字符
🔹 删除字符
🔹 替换字符
3.2 动态规划矩阵
func minDistance(word1 string, word2 string) int {
m, n := len(word1), len(word2)
dp := make([][]int, m+1)
// 初始化及状态转移
// ...
return dp[m][n]
}关键递推：
dp[i][j] = min(dp[i到1][j]+1, dp[i][j到1]+1, dp[i到1][j-1]+cost)
–
🚀 高频面试考点总结
| 题目 | 时间复杂度 | 空间优化技巧 |
|---|---|---|
| 最长回文子串 | O(n²) | 状态压缩至一维数组 |
| 最长公共子序列 | O(mn) | 滚动数组优化 |
| 编辑距离 | O(mn) | 双一维数组交替使用 |
学习建议：
1. 先手动画出DP表格理解状态转移逻辑
2. 用Go语言实现时注意切片初始化的边界条件
3. 在LeetCode提交后对比不同解法的时间/空间消耗
–
掌握这三道题，就能解决80%的字符串动态规划面试题。立即打开LeetCode实战练习，让你的算法能力在秋招季提升200%！
正文完
