手撕代码必备！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状态转移

-

三、编辑距离：字符串变换的成本核算

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)

-

🚀 高频面试考点总结

学习建议：
1. 先手动画出DP表格理解状态转移逻辑
2. 用Go语言实现时注意切片初始化的边界条件
3. 在LeetCode提交后对比不同解法的时间/空间消耗

-

掌握这三道题，就能解决80%的字符串动态规划面试题。立即打开LeetCode实战练习，让你的算法能力在秋招季提升200%！